8. Best Time to Buy and Sell Stock

«Покупай дёшево, продавай дорого. Вся прелесть эффективного алгоритма в том, чтобы не пытаться перебрать все возможные комбинации дней, а просто помнить самую низкую цену из всех, что вы встречали на пути».
— Брайан Керниган

LeetCode 121. Best Time to Buy and Sell Stock (Easy / Core)

Вам дан целочисленный массив prices, где prices[i] — цена акции в день $i$.
Разрешено совершить ровно одну сделку: выбрать один день для покупки акции и другой, более поздний день для её продажи.
Необходимо максимизировать итоговую чистую прибыль. Если получить прибыль невозможно (цены строго падают), следует вернуть 0.

Формулировка и калибровка условий

Вход:  prices = [7, 1, 5, 3, 6, 4]
Вывод: 5
Объяснение: Покупка во 2-й день (цена = 1) и продажа в 5-й день (цена = 6).
Прибыль: 6 - 1 = 5.
(Заметим: покупка во 2-й день и продажа в 1-й день невозможна, так как продать можно только после покупки).

Визуальный Walk-Through: Один линейный проход

Инвариант: двигаясь слева направо, для каждого дня $i$ мы задаём простой вопрос:
«Если я продам акцию сегодня по цене $prices[i]$, когда мне следовало её купить?»
Ответ очевиден: в тот день из прошлого ($0 \dots i-1$), когда цена была минимальной.

flowchart TD
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    Start["prices = [7, 1, 5, 3, 6, 4]<br>minPrice = 7, maxProfit = 0"]:::entry --> D1["День 1 (цена 1):<br>1 < 7 -> Новый minPrice = 1<br>maxProfit = 0"]:::process

    D1 --> D2["День 2 (цена 5):<br>Прибыль: 5 - 1 = 4<br>maxProfit = max(0, 4) = 4"]:::accent
    D2 --> D3["День 3 (цена 3):<br>Прибыль: 3 - 1 = 2<br>maxProfit = 4"]:::process
    D3 --> D4["День 4 (цена 6):<br>Прибыль: 6 - 1 = 5<br>maxProfit = max(4, 5) = 5 (ПИК!)"]:::success
    D4 --> D5["День 5 (цена 4):<br>Прибыль: 4 - 1 = 3<br>maxProfit = 5"]:::process

    D5 --> End["Ответ: 5"]:::success
  

Наивное решение: Квадратичный брутфорс $O(N^2)$

func maxProfitBrute(prices []int) int {
    maxProfit := 0
    for i := 0; i < len(prices)-1; i++ {
        for j := i + 1; j < len(prices); j++ {
            profit := prices[j] - prices[i]
            if profit > maxProfit {
                maxProfit = profit
            }
        }
    }
    return maxProfit
}

При $N = 10^5$ это $5 \cdot 10^9$ итераций — гарантированный Time Limit Exceeded.

Оптимальное решение: Линейный проход за $O(N)$ и $O(1)$ памяти

package main

func maxProfit(prices []int) int {
    if len(prices) < 2 {
        return 0
    }

    minPrice := prices[0]
    maxProfit := 0

    for _, price := range prices[1:] {
        // Вычисляем потенциальную прибыль при продаже сегодня
        profit := price - minPrice
        if profit > maxProfit {
            maxProfit = profit
        }

        // Обновляем исторический минимум цены покупки
        if price < minPrice {
            minPrice = price
        }
    }

    return maxProfit
}

Глубокая связь с алгоритмом Кадане

Если построить массив разниц цен между соседними днями:
$$diff[i] = prices[i+1] - prices[i]$$
то покупка в день $i$ и продажа в день $j$ равна сумме непрерывного отрезка:
$$prices[j] - prices[i] = \sum_{k=i}^{j-1} diff[k]$$
Таким образом, задача о покупке акций математически изоморфна задаче Maximum Subarray (5. Maximum Subarray (Kadane)) на массиве разностей!
Однако прямой подход с поддержанием minPrice элегантнее: он не требует даже неявного построения массива разниц.

Mechanical Sympathy: Ресурсный профиль

1. Zero Allocations: Вся память локализована на стеке вызова в двух регистрах CPU (minPrice и maxProfit).
2. Идеальный последовательный доступ: Доступ к элементам среза происходит строго последовательно, обеспечивая стопроцентное попадание в кэш L1d.
3. Предсказатель переходов (Branch Predictor): Внутри цикла условия просты и однонаправленны, конвейер инструкций CPU работает на предельной частоте.

Резюме

Best Time to Buy and Sell Stock — эталонная задача на отслеживание кумулятивного экстремума на префиксе. Она доказывает, что правильный инвариант позволяет решить задачу за один такт процессора на элемент.

В следующей лекции мы разберем технику слияния отсортированных срезов с конца, предотвращающую перезапись данных: 9. Merge Sorted Array.