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.

有點難，不過和II的解法是一樣的，不過要做兩次掃描，從左往右，再從右往左。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int profit = 0;
        if (prices.size() == 0) {
            return 0;
        }
        vector<int> lefts(prices.size());
        vector<int> rights(prices.size());
        // Scan from left to right, to find current max gap from 0 to ii,
        // and store them in lefts.
        int min = prices[0];
        for (int ii = 1; ii < prices.size(); ii ++) {
            lefts[ii] = std::max(prices[ii] - min, lefts[ii - 1]);        
            min = std::min(prices[ii], min);
        }
        // Scan from right to left, to find current max gap from ii to size - 1,
        // and store them in rights.
        int max = prices[prices.size() - 1];
        for (int ii = prices.size() - 2; ii >= 0; ii --) {
            rights[ii] = std::max(max - prices[ii], rights[ii + 1]);
            max = std::max(prices[ii], max);
        }
        
        // Find the max sum of lefts and rights.
        for (int ii = 0; ii < prices.size(); ii++) {
            profit = std::max(lefts[ii] + rights[ii], profit);
        }
        return profit;      
    }
};