Best Time to Buy and Sell Stock III

Say you have an array for which the i^th 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).

tag: dynamic programming

卖股票第一季让我们完成一次交易，求最大利润；

卖股票第二季让我们完成任意次交易，求最大利润；

这是卖股票第三季，最多完成两次交易，求最大利润。

我们可以这样来考虑：

完成两次交易，且交易的时间不能有重叠。这样我们就可以从时间上把交易分成左右两段，两次交易分别落在左段和右段中。每次交易分别代表着在该段中完成一次交易的最大的利润。也即卖股票第一季的问题。

maxLeftProfit[i]表示从开始到第i天为止，完成一次交易的最大的利润的值；

maxRightProfit[i]表示从第i天到结束为止，完成一次交易的最大的利润的值。

maxLeftProfit[i] + maxRightProfit[i]就表示以第i天为分界线，之前和之后各完成一次交易的最大利润的和。

每个i都计算一次，取最大值。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.empty()){
            return 0;
        }
        size_t n = prices.size();
        vector<int> maxLeftProfit = vector<int>(n, 0);// 在第i天时，左侧交易可达成的最大利润
        vector<int> maxRightProfit = vector<int>(n, 0);// 在第i天时，右侧交易可达成的最大利润
        int minV = prices[0];
        int maxV = prices[n - 1];
        for(int i = 1; i < n; i++){//构建两个数组，maxLeftProfit, maxRightProfit
            maxLeftProfit[i] = max(maxLeftProfit[i - 1], prices[i] - minV);//这实际是sell stock I的代码，完成一次交易可达成的最大利润
            minV = prices[i] < minV? prices[i]: minV;
            
            maxRightProfit[n - i] = max(maxRightProfit[n - i - 1], maxV - prices[n - i]);
            maxV = prices[n - i] > maxV? prices[n - i]: maxV;
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            int thisSum = maxLeftProfit[i] + maxRightProfit[i];
            sum = thisSum > sum? thisSum:sum;
        }
        return sum;
    }
};