State Machine DP

// State: hold = currently holding stock, cash = not holding
// Transition:
//   hold[i] = max(hold[i-1],  cash[i-1] - prices[i])  // keep holding OR buy today
//   cash[i] = max(cash[i-1],  hold[i-1] + prices[i])  // keep not holding OR sell today
// Answer: cash[n-1] (never better to hold at end)

// With unlimited transactions (Best Time II):
var maxProfit = function(prices) {
    let hold = -prices[0], cash = 0;
    for (let i = 1; i < prices.length; i++) {
        const prevHold = hold, prevCash = cash;
        hold = Math.max(prevHold, prevCash - prices[i]);  // buy today
        cash = Math.max(prevCash, prevHold + prices[i]);  // sell today
    }
    return cash;
};

// With cooldown (after selling, can't buy next day):
// States: hold, cooldown (day after sell), rest (can buy)
var maxProfitCooldown = function(prices) {
    let hold = -prices[0], cooldown = 0, rest = 0;
    for (let i = 1; i < prices.length; i++) {
        const [h, c, r] = [hold, cooldown, rest];
        hold = Math.max(h, r - prices[i]);    // buy from "rest" state only
        cooldown = h + prices[i];             // sell → next day is cooldown
        rest = Math.max(r, c);               // rest: was already resting or was in cooldown
    }
    return Math.max(cooldown, rest);
};

// With transaction fee:
var maxProfitFee = function(prices, fee) {
    let hold = -prices[0], cash = 0;
    for (let i = 1; i < prices.length; i++) {
        const [h, c] = [hold, cash];
        hold = Math.max(h, c - prices[i]);
        cash = Math.max(c, h + prices[i] - fee);  // pay fee on sell
    }
    return cash;
};