round: 4
ticket_no: 01
source_no: 19
slug: best-time-to-buy-and-sell-stock-with-transaction-fee
topic: Greedy
difficulty: Medium
leetcode_id: 714
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-15
---

# Билет 01 — Best Time to Buy and Sell Stock with Transaction Fee

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

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

```
Input:  prices = [1,3,2,8,4,9], fee = 2  →  Output: 8
Объяснение: (8 - 1 - 2) + (9 - 4 - 2) = 8

Input:  prices = [1,3,7,5,10,3], fee = 3  →  Output: 6
Объяснение: (10 - 1 - 3) = 6, одна сделка выгоднее двух
```

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

## Ответ

> Дословно из `work-01-...md` (код как написан):

```ruby
def max_profit(prices, fee)
  cash = 0
  hold = -prices[0]

  prices.each do |price|
    cash = max(cash, hold + price - fee)
    hold = max(hold, cash - price)
  end

  cash
end

# сложность: O(n)
# память O(1)
```

## Разбор

**Что верно:**
- Идея DP с двумя состояниями `cash`/`hold` — каноничная, переходы написаны верно: продажа = `hold + price - fee`, покупка = `cash - price`.
- Комиссия вычитается при продаже — по условию LeetCode.
- Результат — `cash` в конце: в финале держать акцию невыгодно.
- Порядок обновления `cash` → `hold` (через уже обновлённый `cash`) корректен при `fee >= 0`: ветка «продал и перекупил в тот же день» (`hold_old - fee`) никогда не выигрывает у `hold_old`.
- Сложность и память названы: O(n) / O(1).
- Прогон на Ruby (после правки синтаксиса): все примеры и edge cases сошлись, включая `[1,2,4,2,5,7,2,4,9,0,9] → 16` (3 сделки: 1→7, 2→9, 0→9).

**Что упущено и ошибки:**
1. ❌ **Код не исполняем:** в Ruby нет функции `max(a, b)` — это метод массива. `cash = max(cash, ...)` падает с `NoMethodError`. Нужно `[cash, hold + price - fee].max`. На реальном интервью с запуском — мгновенный fail.
2. ⚠️ **Двойная обработка первого дня:** `hold = -prices[0]` уже учитывает день 0, а `prices.each` обрабатывает его повторно. Безвредно при `fee >= 0` (первая итерация ничего не меняет), но канонично — `(1...prices.length).each`.
3. ⚠️ **Edge cases не названы** — пустой ответ на обязательную часть формата (единственный системный пробел).

**Эталонная идея:**
Два состояния — `cash` (прибыль без акции) и `hold` (прибыль с акцией, как «деньги после покупки»). Каждый день: `cash = max(cash, hold + price - fee)` (стоять или продать), `hold = max(hold, cash - price)` (держать или купить). Сворачиваем DP-таблицу в два скаляра, т.к. день i зависит только от i-1.

**Время:** O(n) — один проход по ценам, по 2 max на день.

**Память:** O(1) дополнительная (+ ничего на выход).

**Граничные случаи:**
1) Один элемент `[5], fee=2` → 0 (нечего продавать; `hold=-5` не в ответе).
2) Комиссия съедает перепад `[1,2], fee=5` → 0 (лучше не торговать).
3) Растущий рынок `[1,2,3,4,5], fee=1` → 3 (одна сделка 1→5 выгоднее четырёх мелких: каждая даёт 0).
4) `prices.length = 1` — обращение к `prices[0]` безопасно по constraints (`>= 1`).

**Критерии:** идея ✅ · структура данных ✅ · сложность ✅ (названа, но код не проходит Run) · граничные случаи ❌

**Канон сложности:** O(n) / O(1) — совпадает с `complexity-cheat-sheet.md`.

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