714. ...with Transaction Fee

714

MediumStock and State-Machine DPState-machine DP, unlimited transactions minus feeCash/hold state machine with per-sale fee

...with Transaction Fee

Given an array prices where prices[i] is the price of a stock on day i and an integer fee, find the maximum profit. You may complete as many transactions as you like, but each completed transaction (a buy paired with a later sell) incurs the given transaction fee. You may not hold more than one share at a time.

Open official problem prompt ↗

In plain English

Maximize profit with unlimited trades when every completed trade costs a fixed fee.

Picture it like this

Like a market stall that charges a flat commission each time you sell: you only bother flipping goods when the price jump comfortably exceeds the commission, otherwise you hold.

Example

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Why: Buy at 1 sell at 8 nets 7-2=5, buy at 4 sell at 9 nets 5-2=3; total 8.

Constraints

1 <= prices.length <= 5 * 10^41 <= prices[i] < 5 * 10^40 <= fee < 5 * 10^4

Pattern lesson

See the pattern, then code

Cash/hold state machine with per-sale fee

↗

Stock and State-Machine DP

A small set of modes such as holding, free, cooldown, or transactions left.. Track the best profit in two situations each day: cash (not holding a share) and hold (holding one). Selling moves hold to cash and subtracts the fee; buying moves cash to hold. The fee discourages tiny trades so only rises larger than the fee are worth capturing.

New words, made simpleKnow these before the algorithm

cash: Best profit so far while not holding any share.
hold: Best profit so far while holding exactly one share (price already paid).
Transaction fee: A fixed cost charged once per completed buy-sell pair, applied at sale time here.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Greedy sum of gains

Wrong: it charges no fee and over-trades, overstating profit.

Add every positive daily difference like problem 122.

Time O(n)Space O(1)

Best choiceTwo-state rolling DP

Correctly amortizes the fee across each real trade and captures only worthwhile rises.

Keep cash and hold, subtracting the fee when transitioning hold to cash.

Time O(n)Space O(1)

The rule we keep true

Invariant

After each day, cash is the max profit ending that day owning no share, and hold is the max profit ending that day owning one share.

Why this is correct

Reasoning

cash can be reached either by staying in cash or by selling today (hold + price - fee); hold can be reached by staying or by buying today (cash - price). Charging the fee exactly once on the sell transition means each completed trade pays it exactly once, and taking maxima guarantees the optimal decision at every step.

The algorithm in three movesSay these aloud before coding

1Initialize cash = 0 and hold = -infinity

buy at 1: hold = -1

2For each price, set cash = max(cash, hold + price - fee)

sell at 8: cash = 8-1-2 = 5

3Then set hold = max(hold, cash - price)

buy 4, sell 9: cash = 5+5-2 = 8

4Return cash, the best profit holding nothing at the end

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readprice 1

2 · AskBuy or stay?

3 · Update statecash=0, hold=-1

4 · Resulthold becomes -1 (bought at 1).

Key takeaway

Two trades survive the fee: buy 1 / sell 8 and buy 4 / sell 9.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Initial states
Start with 0 profit holding nothing; holding a share is impossible before buying (-inf).
2
Lines 5Sell transition
cash takes the better of staying idle or selling today after paying the fee.
3
Lines 6Buy transition
hold takes the better of keeping the current share or buying today using the just-updated cash.
4
Lines 7Answer
Ending holding a share is never better than having sold, so return cash.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Fee larger than every possible gain yields 0 (never trade)
Single day returns 0
Long gradual climbs are captured as one trade so the fee is paid once, not per day

Common beginner mistakes

Subtracting the fee on both buy and sell, double-charging each trade
Updating hold before cash so the same day's sale leaks into the rebuy incorrectly (order matters; cash first is the standard convention)
Reusing the fee-free greedy from problem 122 and over-trading small rises
Returning hold instead of cash

Check your understanding

Why do we deduct the fee on the sell transition rather than the buy?

...with Transaction Fee

...with Transaction Fee

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stock and State-Machine DP