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)。值得注意的是,反向遍历时,不是求右边的最小值,应该为最大值,应为要先买后卖,数组从左到右的方向为时间轴方向,所以反向遍历时,小值在左边,大值在右边。代码如下:
class Solution {
public:
int maxProfit(vector<int> &prices)
{
int len=prices.size();
if(len==) return ; int profit=; //正向
vector<int> forTrav(len,); //int *forTrav=new int[len];
int lMin=prices[];
int curAns=;
for(int i=;i<len;++i)
{
lMin=min(lMin,prices[i]);
curAns=max(curAns,prices[i]-lMin);
forTrav[i]=curAns;
} //反向
vector<int> resTrav(len,);
int rMax=prices[len-];
curAns=;
for(int i=len-;i>=;--i)
{
rMax=max(rMax,prices[i]);
curAns=max(curAns,rMax-prices[i]);
resTrav[i]=curAns;
} for(int i=;i<len;++i)
{
if(profit<forTrav[i]+resTrav[i])
profit=forTrav[i]+resTrav[i];
} return profit;
}
};
方法二:给出了至多K次的交易次数
参见:Code Gander和Grandyang的博客。