---
round: 3
ticket_no: 22
source_no: 17
slug: best-time-to-buy-and-sell-stock
topic: Greedy
difficulty: Easy
leetcode_id: 121
attempted: true
score:
verdict:
reviewed_at:
---

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

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

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

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

Constraints: `1 <= prices.length <= 10^5`; `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/17-best-time-to-buy-and-sell-stock.md`](../../algo-solutions/01-must-have/07-greedy/17-best-time-to-buy-and-sell-stock.md)