题解 | #买卖股票的最好时机(三)# 别人 很秒的进阶解法

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        // 从非官解中看到一个O(n) O(1) 的解法

        int n = prices.size();
        // 这4个变量是有时间顺序的
        int buy1 = -prices[0], buy2 = -prices[0];
        int sell1 = 0, sell2 = 0;

        for(int i=1; i<n; ++i)
        {
            // 截止到第i天 各操作的最大收益 太妙了
            buy1 = max(buy1, -prices[i]);// 不断更新 第一此买入时的收益  就是找最低成本
            sell1 = max(sell1, buy1+prices[i]);// 最低成本下 那一天第一次卖出收益最大

            buy2 = max(buy2, sell1 - prices[i]); // 在第一次卖出的收益上 寻找哪一天第2次买入收益最大

            sell2 = max(sell2, buy2 + prices[i]);// 在第2次买入基础上 寻找哪天卖出最大
        }

        return sell2;
        
    }
};