309. Best Time to Buy and Sell Stock with Cooldown

Задача

Дан массив цен prices. Максимизируйте прибыль при неограниченных сделках, но с обязательным днём «остывания» после продажи.

Примеры

Пример 1

Input: prices = [1,2,3,0,2]
Output: 3

Пояснение

Транзакции: buy, sell, cooldown, buy, sell.

Пример 2

Input: prices = [1]
Output: 0

Решение

Решение

// Time Complexity: O(n) - один проход по массиву
// Space Complexity: O(1) - используем три переменные
 
function maxProfit(prices) {
    if (prices.length === 0) return 0;
 
    let hold = -prices[0]; // держим акцию
    let sold = -Infinity; // продали сегодня
    let cooldown = 0; // отдыхаем, можем покупать
 
    for (let i = 1; i < prices.length; i++) {
        const newHold = Math.max(hold, cooldown - prices[i]);
        const newSold = hold + prices[i];
        const newCooldown = Math.max(sold, cooldown);
 
        hold = newHold;
        sold = newSold;
        cooldown = newCooldown;
    }
 
    return Math.max(sold, cooldown);
}

Решение 2 (DFS)

/**
 * Рекурсивное решение без мемоизации
 * Время: O(2^n) - экспоненциальная сложность
 * Память: O(n) - глубина стека рекурсии
 */
function maxProfit(prices) {
    const n = prices.length;
 
    // i - текущий день, canBuy - можем ли покупать (1) или продавать (0)
    function dfs(i, canBuy) {
        // Базовый случай: дни закончились
        if (i >= n) return 0;
 
        if (canBuy) {
            // Решение 1: купить сегодня
            const buy = -prices[i] + dfs(i + 1, 0);
            // Решение 2: пропустить
            const skip = dfs(i + 1, 1);
            return Math.max(buy, skip);
        } else {
            // Решение 1: продать (cooldown = i+2)
            const sell = prices[i] + dfs(i + 2, 1);
            // Решение 2: пропустить
            const skip = dfs(i + 1, 0);
            return Math.max(sell, skip);
        }
    }
 
    return dfs(0, 1);
}

Решение 3 (DFS + Memo)

/**
 * Решение с мемоизацией (Dynamic Programming)
 * Время: O(n) - каждое состояние вычисляется один раз
 * Память: O(n) - массив мемоизации n × 2
 */
function maxProfitMemo(prices) {
    const n = prices.length;
    const memo = Array(n).fill(null).map(() => Array(2).fill(-1));
 
    function dfs(i, canBuy) {
        if (i >= n) return 0;
        if (memo[i][canBuy] !== -1) return memo[i][canBuy];
 
        if (canBuy) {
            memo[i][canBuy] = Math.max(
                -prices[i] + dfs(i + 1, 0),
                dfs(i + 1, 1)
            );
        } else {
            memo[i][canBuy] = Math.max(
                prices[i] + dfs(i + 2, 1),
                dfs(i + 1, 0)
            );
        }
 
        return memo[i][canBuy];
    }
 
    return dfs(0, 1);
}