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).
算法思想：
dp1[i]存储前i个元素的最长连续子序列和；
dp2[i]存储i至n-1元素的最长连续子序列和
那么最后答案为max{dp1[i],dp2[i]}，0<=i
class Solution{
public:
int maxProfit(vector
&prices){
if(!prices.size())return 0;
vector
dp1(prices.size()); vector
dp2(prices.size()); dp1[0]=0; int minP=prices[0]; for(int i=1;i
=0;i--){ maxP=max(maxP,prices[i]); dp2[i]=max(dp2[i+1],maxP-prices[i]); } maxP=0; for(int i=0;i