121. Best Time to Buy and Sell Stock

Задача

Дан массив prices , где prices[i] — это цена акции в день i . Вы хотите максимизировать прибыль, выбрав один день для покупки акции и другой день в будущем для её продажи. Верните максимальную прибыль, которую можно получить от этой транзакции. Если получить прибыль невозможно, верните 0.

Примеры

Пример 1

Input: prices = [7,1,5,3,6,4]
Output: 5

Пояснение

Купить в день 2 (цена 1) и продать в день 5 (цена 6), прибыль 6-1 = 5. Продавать раньше покупки нельзя.

Пример 2

Input: prices = [7,6,4,3,1]
Output: 0

Пояснение

Выгодной сделки нет, максимальная прибыль = 0.

Решение

Решение

/**
 * Временная сложность: O(n) - один проход по массиву
 * Пространственная сложность: O(1) - используем только две переменные
 * 
 * @param {number[]} prices - массив цен акций по дням
 * @return {number} - максимальная прибыль
 */
function maxProfit(prices) {
    if (prices.length < 2) {
        return 0;
    }
 
    let minPrice = Infinity; // Минимальная цена покупки
    let maxProfit = 0; // Максимальная прибыль
 
    for (let price of prices) {
        // Обновляем минимальную цену (жадный выбор - всегда покупаем по минимальной)
        minPrice = Math.min(minPrice, price);
 
        // Вычисляем потенциальную прибыль при продаже сегодня
        const currentProfit = price - minPrice;
 
        // Обновляем максимальную прибыль
        maxProfit = Math.max(maxProfit, currentProfit);
    }
 
    return maxProfit;
}
 
// Почему это жадный алгоритм? В этой задаче мы используем жадную стратегию: 
// на каждом шаге запоминаем минимальную цену покупки и вычисляем максимально возможную прибыль. 
// Мы не возвращаемся назад и не пересматриваем решения — просто выбираем лучший вариант на текущий момент. 
// В данном случае жадный подход дает оптимальное решение, 
// потому что для максимизации прибыли достаточно купить по минимальной цене и продать по максимальной после нее.

Решение 2 (Two Pointers + Sliding Window)

/**
 * Временная сложность: O(n)
 * Пространственная сложность: O(1)
 */
function maxProfitSlidingWindow(prices) {
    let left = 0; // Указатель на день покупки
    let maxProfit = 0;
 
    for (let right = 1; right < prices.length; right++) {
        // Если цена упала, двигаем левый указатель
        if (prices[right] < prices[left]) {
            left = right;
        } else {
            // Вычисляем прибыль
            const profit = prices[right] - prices[left];
            maxProfit = Math.max(maxProfit, profit);
        }
    }
 
    return maxProfit;
}

Решение 3 (Brute Force)

/**
 * Временная сложность: O(n²) - вложенные циклы
 * Пространственная сложность: O(1)
 */
function maxProfitBruteForce(prices) {
    let maxProfit = 0;
 
    // Перебираем все возможные дни покупки
    for (let buy = 0; buy < prices.length - 1; buy++) {
        // Перебираем все возможные дни продажи после покупки
        for (let sell = buy + 1; sell < prices.length; sell++) {
            const profit = prices[sell] - prices[buy];
            maxProfit = Math.max(maxProfit, profit);
        }
    }
 
    return maxProfit;
}

Решение 4 (алгоритм Кадане (Kadane's Algorithm))

/**
 * Эта задача — частный случай задачи о максимальной подпоследовательности. Вместо работы с ценами работаем с разностью цен между соседними днями.
 * 
 * Временная сложность: O(n)
 * Пространственная сложность: O(1)
 */
function maxProfitKadane(prices) {
    if (prices.length < 2) return 0;
 
    let maxProfit = 0;
    let currentProfit = 0;
 
    // Вычисляем разность между соседними днями
    for (let i = 1; i < prices.length; i++) {
        const dailyProfit = prices[i] - prices[i - 1];
 
        // Алгоритм Кадане: добавляем к текущей сумме или начинаем заново
        currentProfit = Math.max(0, currentProfit + dailyProfit);
        maxProfit = Math.max(maxProfit, currentProfit);
    }
 
    return maxProfit;
}