309. Best Time to Buy and Sell Stock with Cooldown

/**
 * Refer: 1)
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75927/Share-my-thinking-process/173646
 * 2)
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75927/Share-my-thinking-process
 *
 * On any i-th day, we can buy, sell or cooldown
 *
 * To calculate sell[i]: If we sell on the i-th day, the maximum profit is buy[i
 * - 1] + price, because we have to buy before we can sell. If we cooldown on
 * the i-th day, the maximum profit is same as sell[i - 1] since we did nothing
 * on the i-th day. So sell[i] is the larger one of (buy[i - 1] + price, sell[i
 * - 1])
 *
 * To calculate buy[i]: If we buy on the i-th day, the maximum profit is sell[i
 * - 2] - price, because on the (i-1)th day we can only cooldown. If we cooldown
 * on the i-th day, the maximum profit is same as buy[i - 1] since we did
 * nothing on the i-th day. So buy[i] is the larger one of (sell[i - 2] - price,
 * buy[i - 1])
 *
 * Time Complexity: O(N). Space Complexity: O(1)
 *
 * N = Length of input prices array.
 */
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int sell = 0;
        int prevSell = 0;
        int buy = Integer.MIN_VALUE;
        int prevBuy = Integer.MIN_VALUE;

        for (int price : prices) {
            // buy[i-1]
            prevBuy = buy;

            // buy[i] = Math.max(sell[i-2]-price[i], buy[i-1])
            // sell[i-2]-price[i] -> Buy after a 1 day cooldown
            // buy[i-1] -> cooldown
            buy = Math.max(prevSell - price, prevBuy);

            // sell[i-1];
            prevSell = sell;

            // sell[i] = Math.max(buy[i-1]+price, sell[i-1])
            // buy[i-1]+price -> sell the stock.
            // sell[i-1] -> dcooldown
            sell = Math.max(prevBuy + price, prevSell);
        }

        return sell;
    }
}