0309-best-time-to-buy-and-sell-stock-with-cooldown.js

/**
 * Greedy - State Machine
 * Time O(N) | Space O(1)
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
 * @param {number[]} prices
 * @return {number}
 */
 var maxProfit = (prices) => {
    let [ sold, held, reset ] = [ (-Infinity), (-Infinity), 0 ];

    [ sold, reset ] = search(prices, sold, held, reset);/* Time O(N) */

    return Math.max(sold, reset);
}

var search = (prices, sold, held, reset) => {
    for (const price of prices) {/* Time O(N) */
        const preSold = sold;

        sold = (held + price);
        held = Math.max(held, (reset - price));
        reset = Math.max(reset, preSold);
    }

    return [ sold, reset ];
}

/**
 * DP - Bottom Up
 * Array - Tabulation
 * Time O(N^2) | Space O(N)
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = (prices) => {
    const tabu = initTabu(prices);/* Space O(N) */

    search(prices, tabu);/* Time O(N * N) */

    return tabu[0];
}

var initTabu = (prices) => new Array(prices.length + 2).fill(0);

var search = (prices, tabu) => {
    for (let i = (prices.length - 1); (0 <= i); i--) {/* Time O(N) */
        const prev = buyAndSell(prices, i, tabu);         /* Time O(N) */
        const next = tabu[i + 1];

        tabu[i] = Math.max(prev, next);                       /* Space O(N) */
    }
}

const buyAndSell = (prices, i, tabu, max = 0) => {
    for (let sell = (i + 1); (sell < prices.length); sell++) {/* Time O(N) */
        const profit = ((prices[sell] - prices[i]) + tabu[(sell + 2)]);

        max = Math.max(max, profit);
    }

    return max;
}