题解 | #买卖股票的最好时机(三)#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int n = prices.size();
        vector<int> f(n), g(n);
        for (int i = 1, minV = prices[0]; i < n; i++) {
            f[i] = max(f[i - 1], prices[i] - minV);
            minV = min(prices[i], minV);
        }

        for (int i = n - 2, maxV = prices[n - 1]; i >= 0; i--) {
            g[i] = max(g[i + 1], maxV - prices[i]);
            maxV = max(prices[i], maxV);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = max(res, f[i] + g[i]);
        }

        return res;
    }
};

• 思路：前后缀分解
• f[i]表示在0-i进行一次交易获得的最大利润，g[i]表示在i-n-1进行一次交易获得的最大利润
• f[i]可以由之前minV买入当天卖出转移过来，或者保持不动
• g[i]可以由之后maxV卖出当天买入转移过来，或者保持不动（需要逆向遍历）
• 时间复杂度：O(n)
• 空间复杂度：O(n)