Stock Trading

// Best Time to Buy and Sell Stock with Cooldown
// States: hold (have stock), free (no stock, no cooldown), cool (just sold, cooldown)
function maxProfitWithCooldown(prices) {
    let hold = -Infinity, free = 0, cool = 0;
    for (const price of prices) {
        const prevHold = hold, prevFree = free, prevCool = cool;
        hold = Math.max(prevHold, prevFree - price); // buy from free state
        cool = prevHold + price;                      // sell (enter cooldown)
        free = Math.max(prevFree, prevCool);          // wait in free or exit cooldown
    }
    return Math.max(free, cool);
}

// k transactions: dp[k][0] = max profit, k trans used, not holding
//                 dp[k][1] = max profit, k trans used, holding
function maxProfitKTransactions(k, prices) {
    const n = prices.length;
    if (k >= Math.floor(n / 2)) {
        // Unlimited transactions
        let profit = 0;
        for (let i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i-1]);
        return profit;
    }
    const dp = Array.from({length: k+1}, () => [-Infinity, -Infinity]);
    dp[0][0] = 0;
    for (const price of prices) {
        for (let t = k; t >= 1; t--) {
            dp[t][0] = Math.max(dp[t][0], dp[t][1] + price);   // sell
            dp[t][1] = Math.max(dp[t][1], dp[t-1][0] - price); // buy
        }
    }
    return Math.max(0, ...dp.map(d => d[0]));
}