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

设置一个指针，分别求出前面的最大收益与后面的最大收益，将两者相加，可以提前计算好存在两个数组里以避免重复计算。

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

下面是Best Time to Buy and Sell Stock I的代码，有人说将问题转化为最大连续子序列和的问题，其实不用那样，只要保存当前最小值就可以解决问题。

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4         int n = prices.size();
 5         if (n == 0) return 0;
 6         int max_profit = 0, cur_min = prices[0];
 7         for (int i = 0; i < n; ++i) {
 8             max_profit = max(max_profit, prices[i] - cur_min);
 9             cur_min = min(cur_min, prices[i]);
10         }
11         return max_profit;
12     }
13 };