题解 | #风口的猪-中国牛市#

class Solution {
public:
    /**
     * 计算你能获得的最大收益
     * @param prices Prices[i]即第i天的股价
     * @return 整型
     */
    int calculateMax(vector<int> prices) {
        int n = prices.size();
        if(n < 2) return 0;
        if(n == 2) return max(0, prices[1] - prices[0]);
        
        // 定义四种状态数组
        vector<int> h0s0(n), h1s0(n), h0s1(n), h1s1(n);
        
        // 初始化状态
        h0s0[0] = 0;                                  // 无股票，未卖出
        h1s0[0] = -prices[0];                         // 有1股，未卖出
        h0s1[1] = prices[1] - prices[0];             // 无股票，卖出1次
        h1s1[2] = -prices[2] + prices[1] - prices[0]; // 有1股，卖出1次
        
        int res = 0;
        for(int i = 1; i < n; i++) {
            // 状态转移
            h0s0[i] = h0s0[i-1];                                  // 保持无股票无卖出
            h1s0[i] = max(h1s0[i-1], h0s0[i-1] - prices[i]);     // 保持或买入
            h0s1[i] = max(h0s1[i-1], h1s0[i-1] + prices[i]);     // 保持或卖出第一次
            res = max(res, h0s1[i]);
            
            if(i >= 3) {
                h1s1[i] = max(h1s1[i-1], h0s1[i-1] - prices[i]); // 保持或第二次买入
                res = max(res, h1s1[i-1] + prices[i]);           // 考虑第二次卖出
            }
        }
        
        return res;
    }
};

public class Solution {
    /**
     * 计算你能获得的最大收益
     * @param prices Prices[i]即第i天的股价
     * @return 整型
     */
    public int calculateMax(int[] prices) {
        int n = prices.length;
        if(n < 2) return 0;
        if(n == 2) return Math.max(0, prices[1] - prices[0]);
        
        // 定义四种状态数组
        int[] h0s0 = new int[n];
        int[] h1s0 = new int[n];
        int[] h0s1 = new int[n];
        int[] h1s1 = new int[n];
        
        // 初始化状态
        h0s0[0] = 0;
        h1s0[0] = -prices[0];
        h0s1[1] = prices[1] - prices[0];
        h1s1[2] = -prices[2] + prices[1] - prices[0];
        
        int res = 0;
        for(int i = 1; i < n; i++) {
            // 状态转移
            h0s0[i] = h0s0[i-1];
            h1s0[i] = Math.max(h1s0[i-1], h0s0[i-1] - prices[i]);
            h0s1[i] = Math.max(h0s1[i-1], h1s0[i-1] + prices[i]);
            res = Math.max(res, h0s1[i]);
            
            if(i >= 3) {
                h1s1[i] = Math.max(h1s1[i-1], h0s1[i-1] - prices[i]);
                res = Math.max(res, h1s1[i-1] + prices[i]);
            }
        }
        
        return res;
    }
}