You are given an integer array prices where prices[i] is the price of a stock in dollars on the ith day, and an integer k. You are allowed to make at most k transactions, where each transaction can be either of the following: Normal transaction: Bu

maximumProfit.js

/**
 * @param {number[]} prices
 * @param {number} k
 * @return {number}
 */
var maximumProfit = function(prices, k) {
    // Edge cases
    const n = prices.length;
    if (n === 0 || k === 0) return 0;

    // We will NOT use the "unlimited transactions" shortcut because
    // the problem forbids opening a new position on the same day we close one.
    // That restriction breaks the usual greedy sum of daily deltas.

    // dp[t][i][state]
    // - t: number of COMPLETED transactions so far (0..k)
    // - i: day index (0..n-1)
    // - state:
    //    0 => idle (no position open)
    //    1 => long position open (we bought earlier, still holding)
    //    2 => short position open (we sold earlier, waiting to buy back)
    //
    // Important: opening a position does NOT consume a transaction.
    // Closing a position DOES consume one transaction.
    //
    // Same-day rule:
    // - You cannot close and then open again on the same day.
    //   We enforce this by only allowing closing from day i-1 states into day i.

    const NEG = -Infinity;
    const dp = Array.from({ length: k + 1 }, () =>
        Array.from({ length: n }, () => Array(3).fill(NEG))
    );

    // Base initialization for day 0
    for (let t = 0; t <= k; t++) {
        // Idle with 0 profit
        dp[t][0][0] = 0;

        // Opening positions on day 0 does not consume a transaction
        // Long: we pay prices[0]
        dp[t][0][1] = -prices[0];

        // Short: we receive prices[0]
        dp[t][0][2] = prices[0];
    }

    // Fill DP table
    for (let i = 1; i < n; i++) {
        for (let t = 0; t <= k; t++) {
            // State 0 (idle):
            // - Stay idle from previous day
            let bestIdle = dp[t][i - 1][0];

            // - Close a long (sell today), consuming 1 transaction
            //   We must have been in long at day i-1 with t-1 transactions completed.
            if (t > 0 && dp[t - 1][i - 1][1] !== NEG) {
                bestIdle = Math.max(bestIdle, dp[t - 1][i - 1][1] + prices[i]);
            }

            // - Close a short (buy back today), consuming 1 transaction
            if (t > 0 && dp[t - 1][i - 1][2] !== NEG) {
                bestIdle = Math.max(bestIdle, dp[t - 1][i - 1][2] - prices[i]);
            }

            dp[t][i][0] = bestIdle;

            // State 1 (long open):
            // - Keep holding from yesterday
            // - Open long today from idle yesterday (does NOT consume a transaction)
            let bestLong = dp[t][i - 1][1];
            if (dp[t][i - 1][0] !== NEG) {
                bestLong = Math.max(bestLong, dp[t][i - 1][0] - prices[i]);
            }
            dp[t][i][1] = bestLong;

            // State 2 (short open):
            // - Keep waiting (short still open) from yesterday
            // - Open short today from idle yesterday (does NOT consume a transaction)
            let bestShort = dp[t][i - 1][2];
            if (dp[t][i - 1][0] !== NEG) {
                bestShort = Math.max(bestShort, dp[t][i - 1][0] + prices[i]);
            }
            dp[t][i][2] = bestShort;
        }
    }

    // Result: max profit while idle (no open position) at the end with at most k transactions
    return dp[k][n - 1][0];
};