Best Time to Buy and Sell Stock III
Say you have an array for which the ith 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).
设dpBack[i]为从第一天到第i天的最大的收益
设dpAfter[j]为从第j天到最后一天的最大收益
如何求最大收益可以考虑采用Best Time to Buy and Sell Stock I的方法
注意是最多买两次，也可以只买一次
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n=prices.size();
if(n==)return ;
vector<int> dpBack(n),dpAfter(n);
int maxProfit=;
dpBack[]=;
int left=prices[];
for(int i=;i<n;i++)
{
if(prices[i]>left)
{
if(maxProfit<prices[i]-left) maxProfit=prices[i]-left;
}
else
{
left=prices[i];
}
dpBack[i]=maxProfit;
}
maxProfit=;
dpAfter[n-]=;
int right=prices[n-];
for(int j=n-;j>=;j--)
{
if(prices[j]<right)
{
if(maxProfit<right-prices[j]) maxProfit=right-prices[j];
}
else
{
right=prices[j];
}
dpAfter[j]=maxProfit;
}
int result=;
for(int i=;i<n-;i++)
{
if(dpBack[i]+dpAfter[i+]>result) result=dpBack[i]+dpAfter[i+];
if(result<dpBack[i+]) result=dpBack[i+];
}
return result;
}
};