class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2) return 0;
        int buy1 = -prices[0]; // 第 0 天买入
        int sell1 = 0;         // 第 0 天买入又卖出
        int buy2 = -prices[0]; // 第 0 天买入卖出再买入
        int sell2 = 0;         // 第 0 天买入卖出再买入再卖出
        
        for(int i = 1; i < n; i++){
            // 更新第一次买入的最大利润
            buy1 = Math.max(buy1, -prices[i]); 
            // 更新第一次卖出的最大利润
            sell1 = Math.max(sell1, buy1 + prices[i]);
            // 更新第二次买入的最大利润 (基于第一次卖出的利润)
            buy2 = Math.max(buy2, sell1 - prices[i]);
            // 更新第二次卖出的最大利润 (基于第二次买入的利润)
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        // 最终结果是完成两次交易的最大利润
        return sell2;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2) return 0;
        
        // firstRound[i] = max profit in prices[0...i] with at most 1 transaction
        int[] firstRound = new int[n];
        int minFirstRoundPrice = prices[0];
        // firstRound[0] = 0; (already initialized)
        for(int i = 1; i < n; i++){
            minFirstRoundPrice = Math.min(prices[i], minFirstRoundPrice);
            firstRound[i] = Math.max(firstRound[i-1], prices[i] - minFirstRoundPrice);
        }
        
        // secondRound[i] = max profit in prices[i...n-1] with at most 1 transaction
        int[] secondRound = new int[n];
        int maxSecondRoundPrice = prices[n - 1];
        // secondRound[n-1] = 0; (already initialized)
        for(int j = n - 2; j >= 0; j--){
            maxSecondRoundPrice = Math.max(maxSecondRoundPrice, prices[j]);
            // Profit if selling at maxSecondRoundPrice having bought at prices[j]
            // Or the max profit achievable starting from j+1
            secondRound[j] = Math.max(secondRound[j + 1], maxSecondRoundPrice - prices[j]);
        }
        
        // Combine the results
        int maxProfit = 0;
        // The max profit is the sum of max profit from first round ending at k
        // and max profit from second round starting at k.
        // Note: a single transaction is also covered when either firstRound[k] or secondRound[k] is 0.
        // The maximum of firstRound[n-1] already covers the single transaction case.
        // The loop correctly covers splitting the two transactions.
        for(int k = 0; k < n ; k++){
            // Special case: if k=0, profit is secondRound[0] (one transaction in [0, n-1])
            // Special case: if k=n-1, profit is firstRound[n-1] (one transaction in [0, n-1])
            // These cases are handled correctly by the loop and array initialization.
             maxProfit = Math.max(maxProfit, firstRound[k] + secondRound[k]);
        }
        // Does max(firstRound[k] + secondRound[k]) cover the single transaction case correctly?
        // Yes, because if the max profit comes from a single transaction, say in [0, m],
        // then firstRound[m] will hold this max profit. When k=m, we consider firstRound[m] + secondRound[m].
        // Since secondRound[m] >= 0, this sum is at least firstRound[m].
        // If the single optimal transaction is in [p, n-1], then secondRound[p] holds it.
        // When k=p, we consider firstRound[p] + secondRound[p]. Since firstRound[p] >=0, the sum is >= secondRound[p].
        // The absolute maximum single transaction profit is captured in firstRound[n-1] and secondRound[0].
        // maxProfit will eventually compare against firstRound[n-1] + secondRound[n-1] = firstRound[n-1] + 0
        // and firstRound[0] + secondRound[0] = 0 + secondRound[0].
        // So, the single transaction case is implicitly covered.

        return maxProfit;
    }
}