LeetCode OJ:Best Time to Buy and Sell Stock III

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