[LeetCode]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).

和Best Time to Buy and Sell Stock很接近，需要维护两个vector使得两次交易一次在区间【0-i】，一次在区间【i，n-1】。

每个区间内的求解最大收益的方法和Best Time to Buy and Sell Stock几乎一样。

取两个区间收益和最大的的结果为最终结果。

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         if (prices.size()<2) return 0;
 5         int result=0;
 6         int n = prices.size();
 7         vector<int> left(n,0);
 8         vector<int> right(n,0);
 9         int cur_min = prices[0];
10         int cur_result = 0;
11         for(int i=1;i<n;i++)
12         {
13             cur_result = max(cur_result,prices[i]-cur_min);
14             left[i] = cur_result;
15             cur_min = min(cur_min,prices[i]);
16         }
17         int cur_max = prices[n-1];
18         cur_result = 0;
19         for(int i=n-2;i>0;i--)
20         {
21             cur_result = max(cur_result,cur_max-prices[i]);
22             right[i] = cur_result;
23             cur_max = max(cur_max,prices[i]);
24         }
25         for(int i=1;i<n;i++)
26         {
27             result = max(result,left[i]+right[i]);
28         }
29         return result;
30     }
31 };