例题分析 -- 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).

***************************************************************************

分析：

    设状态f(i)，表示区间[0，i]的最大利润，状态g(i)，表示区间[i,n]的最大利润，则最终答案为max(f(i) +g(i))

***************************************************************************

代码：

    int maxProfit(vector &prices) {
        if (prices.size() < 2) return 0;
        vector f(prices.size(), 0);
        vector g(prices.size(), 0);
        for (int i = 1, valley = prices[0]; i < prices.size(); ++i) {
            valley = min(valley, prices[i]);
            f[i] = max(f[i - 1], prices[i] - valley);
        }
        for (int i = prices.size() - 2, peak = prices[prices.size() - 1]; i >= 0; --i) {
            peak = max(peak, prices[i]);
            g[i] = max(g[i], peak - prices[i]);
        }
        int max_profit = 0;
        for (int i = 0; i < prices.size(); ++i)
            max_profit = max(max_profit, f[i] + g[i]);
        return max_profit;
    }