---
title: Best Time to Buy and Sell Stock
difficulty: Easy
category: Greedy
leetcode_id: 121
revision_count: 2
last_revision: 2026-09-12
---

# Best Time to Buy and Sell Stock

> **LeetCode:** [#121](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
> **Сложность:** Easy
> **Категория:** Greedy

## Условие

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

```
Input:  prices = [7, 1, 5, 3, 6, 4]  →  Output: 5 (купить в день 2 по 1, продать в день 5 по 6)
Input:  prices = [7, 6, 4, 3, 1]     →  Output: 0 (нет прибыльной сделки)
```

## Ключевая идея

За один проход отслеживаем минимальную цену `min_price` из всех просмотренных дней. Для каждого дня прибыль = `price - min_price` — это максимальная прибыль, которую можно получить, продав в этот день. Фиксируем `max_profit` как максимум из всех таких значений.

## Оценка сложности

- **Время:** O(n) — один проход по массиву
- **Память:** O(1) — только два скаляра

## Решение (Ruby)

```ruby
# @param {Integer[]} prices
# @return {Integer}
def max_profit(prices)
  min_price = Float::INFINITY
  max_profit = 0

  prices.each do |price|
    min_price = price if price < min_price
    profit = price - min_price
    max_profit = profit if profit > max_profit
  end

  max_profit
end
```

## Разбор на примере

```
prices = [7, 1, 5, 3, 6, 4]
min_price = +∞, max_profit = 0

i=0  price=7  min_price=7   profit=0  max_profit=0
i=1  price=1  min_price=1   profit=0  max_profit=0
i=2  price=5  min_price=1   profit=4  max_profit=4
i=3  price=3  min_price=1   profit=2  max_profit=4
i=4  price=6  min_price=1   profit=5  max_profit=5
i=5  price=4  min_price=1   profit=3  max_profit=5

Result: 5
```

```
prices = [7, 6, 4, 3, 1]
min_price = +∞, max_profit = 0

i=0  price=7  min_price=7   profit=0  max_profit=0
i=1  price=6  min_price=6   profit=0  max_profit=0
i=2  price=4  min_price=4   profit=0  max_profit=0
i=3  price=3  min_price=3   profit=0  max_profit=0
i=4  price=1  min_price=1   profit=0  max_profit=0

Result: 0
```

## Edge Cases

- **Убывающий рынок**: `[7, 6, 4, 3, 1]` — min_price всё время меньше, прибыль всегда 0 → результат 0.
- **Один элемент**: `[5]` — невозможно продать, результат 0.
- **Все цены равны**: `[3, 3, 3]` — прибыль 0.
- **Очень большие числа**: в пределах 32-bit int по условию LeetCode, но Ruby с этим справится.
- **Цена падает, потом растёт**: классический случай выше.

## Типичные ошибки

1. ❌ **Инициализировать `min_price` нулём** — тогда для `[5, 4, 3, 2, 1]` min_price будет больше всех цен (все цены меньше нуля не бывают), прибыль станет 0 — но и правильный ответ 0, так что ошибка не проявится. Ошибочно, когда есть цены ниже 0 — но по условию цены ≥ 0. **Тем не менее** `Float::INFINITY` — правильная идиома, не зависящая от диапазона.
2. ❌ **Путать покупку и продажу**: обновлять `max_profit` до обновления `min_price` — для `[2, 1, 4]` получим max_profit = 2 (продажа по 4 минус min_price=2 на момент проверки), хотя правильный ответ 3 (купить по 1, продать по 4).
3. ❌ **Проверять только глобальный min и max** — максимальная цена может быть до минимальной (например, `[5, 1, 2]`: max=5 до min=1 — сделка невозможна). Решение за один проход корректно обрабатывает порядок.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (два вложенных цикла) | O(n²) | O(1) | Проверяем все пары (i < j) |
| **One-pass (min_price + max_profit)** | **O(n)** | **O(1)** | **финальное решение** |

Brute-force — первая мысль, но O(n²) фейлится на больших данных (10⁵+ элементов). Оптимальное решение — O(n), O(1): один проход, никаких допструктур.

## Заметки после повторения

_— Заполняется после каждой тренировки._