---
title: Best Time to Buy and Sell Stock with Transaction Fee
difficulty: Medium
category: Greedy
leetcode_id: 714
revision_count: 1
last_revision: 2026-09-12
---

# Best Time to Buy and Sell Stock with Transaction Fee

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

## Условие

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

```
Input:  prices = [1, 3, 2, 8, 4, 9], fee = 2  →  Output: 8
  Купить по 1, продать по 8 (с учётом fee=2) → +5
  Купить по 4, продать по 9 (с учётом fee=2) → +3
  Итого: 5 + 3 = 8

Input:  prices = [1, 3, 7, 5, 10, 3], fee = 3 →  Output: 6
  Купить по 1, продать по 7 (fee=3) → +3
  Купить по 5, продать по 10 (fee=3) → +2
  Итого: 3 + 2 = 5? Нет — лучше одна сделка: купить по 1, продать по 10 (fee=3) → +6
```

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

DP с двумя состояниями: `cash` — максимальная прибыль на текущий день, если у нас **нет** акции на руках; `hold` — максимальная прибыль, если акция **есть** на руках. Комиссия вычитается при переходе `hold → cash` (т.е. при продаже). На каждом дне обновляем состояния за O(1).

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

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

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

```ruby
# @param {Integer[]} prices
# @param {Integer} fee
# @return {Integer}
def max_profit(prices, fee)
  cash = 0               # нет акции на руках
  hold = -prices[0]      # купили в первый день

  (1...prices.length).each do |i|
    cash = [cash, hold + prices[i] - fee].max   # либо не делаем ничего, либо продаём
    hold = [hold, cash - prices[i]].max          # либо держим, либо покупаем с текущим cash
  end

  cash
end
```

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

```
prices = [1, 3, 2, 8, 4, 9], fee = 2
cash = 0, hold = -1

i=1  price=3  cash = max(0,  -1 + 3 - 2) = max(0,  0)  →  0
              hold = max(-1,  0 - 3)        = max(-1, -3) → -1
i=2  price=2  cash = max(0,  -1 + 2 - 2) = max(0, -1)   →  0
              hold = max(-1,  0 - 2)        = max(-1, -2) → -1
i=3  price=8  cash = max(0,  -1 + 8 - 2) = max(0,  5)   →  5   ← продали по 8
              hold = max(-1,  5 - 8)        = max(-1, -3) → -1
i=4  price=4  cash = max(5,  -1 + 4 - 2) = max(5,  1)   →  5
              hold = max(-1,  5 - 4)        = max(-1,  1) →  1   ← купили по 4
i=5  price=9  cash = max(5,   1 + 9 - 2) = max(5,  8)   →  8   ← продали по 9
              hold = max(1,   8 - 9)        = max(1, -1)  →  1

Result: 8
```

```
prices = [1, 3, 7, 5, 10, 3], fee = 3
cash = 0, hold = -1

i=1  price=3  cash = max(0,  -1 + 3 - 3) = max(0, -1)   →  0
              hold = max(-1,  0 - 3)        = max(-1, -3) → -1
i=2  price=7  cash = max(0,  -1 + 7 - 3) = max(0,  3)   →  3
              hold = max(-1,  3 - 7)        = max(-1, -4) → -1
i=3  price=5  cash = max(3,  -1 + 5 - 3) = max(3,  1)   →  3
              hold = max(-1,  3 - 5)        = max(-1, -2) → -1
i=4  price=10 cash = max(3,  -1 + 10 - 3) = max(3,  6)  →  6   ← продали по 10 (одна сделка 1→10 = 10-1-3 = 6)
              hold = max(-1,  6 - 10)       = max(-1, -4) → -1
i=5  price=3  cash = max(6,  -1 + 3 - 3) = max(6, -1)   →  6
              hold = max(-1,  6 - 3)        = max(-1,  3) →  3

Result: 6
```

## Edge Cases

- **Один элемент**: `[5], fee=2` — нельзя продать → cash=0, hold=-5 → ответ 0.
- **Все цены одинаковы**: `[3, 3, 3], fee=1` — нет перепадов, комиссия съест любую прибыль → 0.
- **Комиссия больше перепада**: `[1, 2], fee=5` — даже максимальный перепад 1 меньше комиссии → 0.
- **Растущий рынок**: `[1, 2, 3, 4, 5], fee=1` — каждая сделка даёт +1 (2-1-1=0, 3-2-1=0…) → лучше одна сделка 1→5: 5-1-1=3. DP найдёт 3.
- **Только одна прибыльная сделка**: `[10, 1, 5], fee=2` — купить по 1, продать по 5 даёт 2, но не стоит: 5-1-2=2; `[10, 1, 8], fee=2` — 8-1-2=5 — стоит.

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

1. ❌ **Комиссию вычитать при покупке, а не при продаже** — в условии сказано «per transaction», но на LeetCode комиссия взимается при продаже. Если вычесть при покупке, ответ может отличаться (хотя для symmetric fee результат тот же).
2. ❌ **Путать с Stock II (без комиссии)** — просто суммировать положительные diff не работает: из-за комиссии может быть выгоднее держать одну сделку, чем две маленьких.
3. ❌ **Обновлять состояния последовательно без учёта, что cash на этом шаге уже обновлён** — в Ruby-решении выше порядок обновления `cash`, потом `hold` не критичен: `hold` использует `cash` на текущем шаге, что эквивалентно «купить с текущим cash», т.е. продать можно на этом же шаге, потом сразу купить. Это корректно (продажа и покупка в один день допустимы, если сначала продать, потом купить).

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

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (все последовательности сделок) | O(2ⁿ) | O(1) | 2ⁿ вариантов — непрактично |
| DP с массивом (states[day][0/1]) | O(n) | O(n) | Явное хранение всех дней — избыточно |
| **DP с двумя состояниями (cash/hold)** | **O(n)** | **O(1)** | **финальное решение** — оптимально |

DP с массивом — та же идея, но требует массива размером n×2. Оптимальное решение сворачивает состояния в два скаляра, что снижает память с O(n) до O(1). Важно помнить, что это частный случай общего подхода к задачам «Best Time to Buy and Sell Stock» с ограничениями: для Stock III (2 транзакции) или Stock IV (k транзакций) понадобится уже массив k×2 состояний.

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

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