Best Time to Buy and Sell Stock (Easy)

Бытовая аналогия

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

Условие

Дан списокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. цен prices, где prices[i] — цена акции в день i. Купить можно один раз и продать позже. Верните максимальную прибыль; если заработать нельзя — 0.

Пример: [7, 1, 5, 3, 6, 4] → 5 (купить за 1, продать за 6).

Идея

Идём по дням и держим в памяти минимальную цену, что встречалась раньше. В каждый день считаем прибыль «сегодня продать − минимум до сегодня» и обновляем лучший результат. Один проход — O(n).

Что делает каждая строка

• min_price = float("inf") — стартовый «минимум», заведомо больше любой реальной цены, чтобы первая же цена его перебила.
• best = 0 — лучшая прибыль; если заработать нельзя, останется 0.
• if p < min_price — нашли новую самую низкую цену для покупки — запоминаем.
• else: best = max(best, p - min_price) — иначе считаем прибыль «продать сегодня после покупки на минимуме» и обновляем рекорд.

Ответ — 8. Хотя пара (3 → 8) даёт прибыль 5, позже цена падает до 1, и покупка за 1 с продажей за 9 даёт 8. Важно: продавать можно только после покупки, поэтому 1 (день 3) и 9 (день 4) — корректная пара, а вот купить за 1 и «продать» за 8 из прошлого нельзя.

⚠️ Частые ошибки новичков

Типичная ошибка — считать ответ как max(prices) - min(prices). Это неверно, если максимум стоит раньше минимума (продать до покупки нельзя). Например, для [7, 6, 4, 3, 1] такой подход дал бы 7 - 1 = 6, хотя правильный ответ — 0. Запустите ниже и убедитесь.