---
title: Best Time to Buy and Sell Stock II
difficulty: Medium
category: Greedy
leetcode_id: 122
revision_count: 1
last_revision: 2026-09-12
---

# Best Time to Buy and Sell Stock II

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

## Условие

Дан массив `prices`, где `prices[i]` — цена акции в i-й день. Можно совершить **неограниченное количество сделок**: купить, затем продать, затем снова купить (но не более одной акции одновременно, т.е. продать перед следующей покупкой). Вернуть максимальную возможную суммарную прибыль.

```
Input:  prices = [7, 1, 5, 3, 6, 4]  →  Output: 7
  Купить в день 2 по 1, продать в день 3 по 5 → +4
  Купить в день 4 по 3, продать в день 5 по 6 → +3
  Итого: 4 + 3 = 7

Input:  prices = [1, 2, 3, 4, 5]      →  Output: 4
  Купить в день 1 по 1, продать в день 5 по 5 → +4
  (эквивалентно: все дневные перепады 1→2 + 2→3 + 3→4 + 4→5 = 1+1+1+1 = 4)

Input:  prices = [7, 6, 4, 3, 1]      →  Output: 0
  Нет восходящего движения — никакая сделка не принесёт прибыль.
```

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

Любая последовательность сделок даёт суммарную прибыль, равную сумме всех положительных перепадов `prices[i] - prices[i-1]` на временной шкале. Поэтому достаточно за один проход прибавлять к ответу каждый положительный перепад — это и есть максимальная прибыль. Покупаем в каждый локальный минимум, продаём в следующий локальный максимум.

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

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

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

```ruby
# @param {Integer[]} prices
# @return {Integer}
def max_profit(prices)
  profit = 0

  (1...prices.length).each do |i|
    profit += prices[i] - prices[i - 1] if prices[i] > prices[i - 1]
  end

  profit
end
```

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

```
prices = [7, 1, 5, 3, 6, 4]
profit = 0

i=1  price=1  prev=7  diff=-6  →  не суммируем
i=2  price=5  prev=1  diff=+4  →  profit += 4 → profit=4
i=3  price=3  prev=5  diff=-2  →  не суммируем
i=4  price=6  prev=3  diff=+3  →  profit += 3 → profit=7
i=5  price=4  prev=6  diff=-2  →  не суммируем

Result: 7
```

## Edge Cases

- **Растущий рынок**: `[1, 2, 3, 4, 5]` — каждый шаг положительный → суммируем все +1 → ответ 4.
- **Падающий рынок**: `[7, 6, 4, 3, 1]` — нет положительных перепадов → ответ 0.
- **Один элемент**: `[5]` — цикл не выполняется → profit = 0 (нельзя продать).
- **Два элемента**: `[1, 5]` — profit = 4 (купить по 1, продать по 5). `[5, 1]` — profit = 0.
- **Плато**: `[3, 3, 3]` — нет положительных перепадов → ответ 0.
- **Все цены одинаковые**: как плато — 0.
- **Колебания**: `[1, 4, 2, 5, 3, 6]` — суммируем 1→4 (+3), 2→5 (+3), 3→6 (+3) = 9. Можно продавать на каждом пике и сразу покупать на следующем спаде.

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

1. ❌ **Решать как Stock I (искать один глобальный минимум и максимум)** — в Stock II можно делать много сделок, и сумма небольших перепадов может превысить одну большую сделку. Пример: `[1, 3, 2, 6]` — одна сделка (1→6) = 5, а две сделки (1→3 + 2→6) = 2 + 4 = 6 > 5.
2. ❌ **Путать с variant «with cooldown» или «with transaction fee»** — эта задача чистая: нет комиссий, нет задержек, нет лимита сделок.
3. ❌ **Сложные конструкции с ручной куплей/продажей** — задача решается без хранения состояния «купил/продал»: достаточно суммировать положительные diff. Люди пишут лишний код, не замечая простой greedy.

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

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (все подпоследовательности) | O(2ⁿ) | O(1) | 2ⁿ вариантов сделок — непрактично |
| DP (peak/valley detection) | O(n) | O(1) | Ищем локальные минимумы и максимумы, суммируем разницы — то же самое, больше кода |
| **Sum of positive diffs (greedy)** | **O(n)** | **O(1)** | **финальное решение** — минимальное и самое чистое |

Peak/valley detection — та же сложность, но больше кода: два указателя ищем valley, потом peak, прибавляем разницу и повторяем. На практике sum-of-positive-diffs даёт тот же результат и короче. LeetCode-маркировка Medium здесь скорее формальная — задача решается в 3 строки.

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

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