leetcode 123. 买卖股票的最佳时机 III

题目：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

O(N)的算法：

f[i] = max(max(0, prices[i] - min(prices[0], prices[1], ... , prices[i - 1)), f[i - 1]);

g[i] = max(max(0, max(prices[i + 1], prices[i + 2], ... , prices[n - 1])), g[i + 1);

计算最大的 f[i - 1] + g[i] 即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = (int) prices.size();
        vector<int> f(n);
        vector<int> g(n);
        
        {
            int min = prices[0];
            f[0] = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] < min) min = prices[i];
                if (prices[i] - min > 0) {
                    f[i] = prices[i] - min;
                } else {
                    f[i] = 0;
                }
                if (f[i - 1] > f[i]) {
                    f[i] = f[i - 1];
                }
            }
        }
        {
            int max = prices[n - 1];
            g[n - 1] = 0;
            for (int i = n - 2; i >= 0; i--) {
                if (prices[i] > max) max = prices[i];
                if (max - prices[i] > 0) {
                    g[i] = max - prices[i];
                } else {
                    g[i] = 0;
                }
                if (g[i + 1] > g[i]) {
                    g[i] = g[i + 1];
                }
            }
        }
        int t;
        int ret = g[0];
        for (int i = 1; i < n; i++) {
            t = f[i - 1] + g[i];
            if (t > ret) {
                ret = t;
            }
        }
        
        return ret;
    }
};