---
round: 3
ticket_no: 30
source_no: 19
slug: best-time-to-buy-and-sell-stock-with-transaction-fee
topic: Greedy
difficulty: Medium
leetcode_id: 714
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 30 — 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
```

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

## Ответ

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

## Разбор

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

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

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

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

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

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

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

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

**Разбор задачи:** [`../../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)