首页 > 代码库 > [Leetcode] Best time to buy and sell stock iii 买卖股票的最佳时机

[Leetcode] Best time to buy and sell stock iii 买卖股票的最佳时机

Say you have an array for which the i th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: 
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

 题意:最多两次买卖,而且下一次必须在上一次结束之后。动态规划

方法一:

常规思路是,将整个数组分为两个段,使前半段获得的最大利润加上后半段获得的最大利润的和最大。这就涉及到一个如何分段的问题了?我们可以遍历一遍数组,以每个元素为分结点(分界点,即某天可以先卖出第一次的,再买入第二的),找到和最大的情况。所以原问题就如何分别求得前后两段的最大利润了,而求某一段的最大利润,可参考Best time to buy and sell stock。因为前一段的终点和后一段的起点不确定,若是从左往右以每个点作为元素遍历一次,求出对应的最大利润,这样就要做两次遍历n+ n-1+ n-2...0,时间复杂度就为O(n^2),变成暴力解法。这里提供的思路是,将数组正、反个遍历一次,将各个点的最大利润分别存入两个数组中,这样最后只要以每个元素为界点再遍历一次,3*n,时间复杂度为O(n)。值得注意的是,反向遍历时,不是求右边的最小值,应该为最大值,应为要先买后卖,数组从左到右的方向为时间轴方向,所以反向遍历时,小值在左边,大值在右边。代码如下:

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) 
 4     {
 5         int len=prices.size();
 6         if(len==0)  return 0;
 7 
 8         int profit=0;
 9 
10         //正向
11         vector<int> forTrav(len,0);     //int  *forTrav=new int[len];
12         int lMin=prices[0];
13         int curAns=0;
14         for(int i=0;i<len;++i)
15         {
16             lMin=min(lMin,prices[i]);
17             curAns=max(curAns,prices[i]-lMin);
18             forTrav[i]=curAns;
19         }    
20 
21         //反向
22         vector<int> resTrav(len,0);
23         int rMax=prices[len-1];
24         curAns=0;
25         for(int i=len-1;i>=0;--i)
26         {
27             rMax=max(rMax,prices[i]);
28             curAns=max(curAns,rMax-prices[i]);
29             resTrav[i]=curAns;
30         }
31 
32         for(int i=0;i<len;++i)
33         {
34             if(profit<forTrav[i]+resTrav[i])
35                 profit=forTrav[i]+resTrav[i];
36         }
37 
38         return profit;
39     }
40 };

方法二:给出了至多K次的交易次数

参见:Code Gander和Grandyang的博客。

 

[Leetcode] Best time to buy and sell stock iii 买卖股票的最佳时机