DSA Tracker

Visualize

Best Time to Buy and Sell Stock with Transaction Fee

Two rolling states per day: cash (no stock) and hold (holding stock)

time O(n)space O(1)

At the end of any day you are in exactly one of two states: holding no stock (cash) or holding stock (hold). Each day's best cash is either yesterday's cash, or selling today's stock (yesterday's hold, plus today's price, minus the fee). Each day's best hold is either yesterday's hold, or buying today (yesterday's cash, minus today's price). The fee only ever appears on the sell side, so it is charged exactly once per completed trade no matter how many trades happen.

Details

Animated on: prices = [1,3,2,8,4,9], fee = 2 — unlimited transactions, each sale pays the fee. Find the max profit.

Problem:Best Time to Buy and Sell Stock with Transaction FeeMedium

Two rolling states per day: cash (no stock) and hold (holding stock)

step 1 / 12

cash/hold over prices [1, 3, 2, 8, 4, 9], fee = 2

Day 0: cash[0] = 0 (never traded), hold[0] = -1 (bought immediately at 1, fee only charged on sell).

Pseudocode
1FUNCTION maxProfit(prices, fee):
2  cash <- 0
3  hold <- -prices[0]
4  FOR i FROM 1 TO LENGTH(prices) - 1:
5    newCash <- MAX(cash, hold + prices[i] - fee)
6    newHold <- MAX(hold, cash - prices[i])
7    cash <- newCash
8    hold <- newHold
9  RETURN cash

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. Day 0: cash[0] = 0 (never traded), hold[0] = -1 (bought immediately at 1, fee only charged on sell).
  2. Day 1, price 3: selling beats staying in cash — hold[0] + 3 - fee(2) = 0 > cash[0] = 0, so cash[1] = 0.
  3. Day 1: cash[0] - 3 = -3 is worse than just keeping yesterday's holding, hold[0] = -1, so hold[1] stays -1.
  4. Day 2, price 2: selling would net -1 (hold[1] + 2 - fee), worse than just carrying cash[1] = 0, so cash[2] stays 0.
  5. Day 2: cash[1] - 2 = -2 is worse than just keeping yesterday's holding, hold[1] = -1, so hold[2] stays -1.
  6. Day 3, price 8: selling beats staying in cash — hold[2] + 8 - fee(2) = 5 > cash[2] = 0, so cash[3] = 5.
  7. Day 3: cash[2] - 8 = -8 is worse than just keeping yesterday's holding, hold[2] = -1, so hold[3] stays -1.
  8. Day 4, price 4: selling would net 1 (hold[3] + 4 - fee), worse than just carrying cash[3] = 5, so cash[4] stays 5.
  9. Day 4: buying in beats carrying yesterday's position — cash[3] - 4 = 1 > hold[3] = -1 (note: cash[3], NOT the just-updated cash[4] = 5 — buying and selling the same day must never share one fee).
  10. Day 5, price 9: selling beats staying in cash — hold[4] + 9 - fee(2) = 8 > cash[4] = 5, so cash[5] = 8.
  11. Day 5: cash[4] - 9 = -4 is worse than just keeping yesterday's holding, hold[4] = 1, so hold[5] stays 1.
  12. End of the array while holding stock is worthless, so the answer is cash[5] = 8.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Best Time to Buy and Sell Stock with Transaction Fee in the editorAll Dynamic Programming problemsBack to roadmap