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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> f(n+1),g(n+1);
        //预处理f，f[i]表示前i天交易的最大值
        for(int i=1,min_price=INT_MAX;i<=n;i++)//根据当前是否卖出划分
        {
            min_price=min(min_price,prices[i-1]);
            f[i]=max(f[i-1],prices[i-1]-min_price);
        }
        //预处理g，g[i]表示i天买入，[i~n-1]卖出的最大值
        for(int i=n-1,max_price=-1;i>=0;i--)
        {
            max_price=max(max_price,prices[i]);
            g[i]=max_price-prices[i];
        }
        //枚举交易分界点
        int res=0;
        for(int i=0;i<n;i++)
            res=max(res,f[i]+g[i]);
        return res;
    }
};