---
round: 3
ticket_no: 20
source_no: 18
slug: best-time-to-buy-and-sell-stock-ii
topic: Greedy
difficulty: Medium
leetcode_id: 122
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 20 — Best Time to Buy and Sell Stock II

## Условие (как предъявлено)

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

```
Input:  prices = [7,1,5,3,6,4]  →  Output: 7
Input:  prices = [1,2,3,4,5]    →  Output: 4
Input:  prices = [7,6,4,3,1]    →  Output: 0
```

Constraints: `1 <= prices.length <= 3 * 10^4`; `0 <= prices[i] <= 10^4`.

## Ответ

> Задача решается в один проход. Значит, здесь, ну, мы должны сделать счётчик накопления прибыли. Вот, берём первый элемент — это у нас будет кандидат в покупку. Значит, потом переходим, то есть, у нас сейчас состояние, что акций на руке нету. Мы сравниваем. Потом переходим к следующему элементу. Второй элемент, например, меньше. Тогда он становится кандидатом к покупке. Итак, доходим до места, где бац, после одного элемента, после одной цены идёт повышение цены. Всё, тогда мы переходим в состояние, что у нас акции на руках, и мы теперь назначаем эту позицию — это кандидат к продаже. Вот и так доходим, идём дальше, смотрим: цена повышается, повышается, как только она перестала повышаться. Точнее, так, как только она снизилась, вот в этот момент мы понимаем, что это был кандидат к продаже, продаём, то есть фиксируем прибыль, сохраняем, и теперь у нас кандидат к покупке. То есть меняем состояние снова, и так далее. Доходим до конца. Вот, ну и, соответственно, если у нас там в конце последний элемент сравнивать уже не с чем, то мы порядок состояния. То есть, если у нас было состояние, что у нас акции на руках, мы принимаем решение: вообще нужно было покупать или нет, но либо наоборот, в общем, понятно, от ситуации там нужно кончик тоже правильно отработать.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/01-must-have/07-greedy/18-best-time-to-buy-and-sell-stock-ii.md`](../../algo-solutions/01-must-have/07-greedy/18-best-time-to-buy-and-sell-stock-ii.md)