Pattern visualizer

Best Time to Buy and Sell Stock with Transaction Fee

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. Animated on: prices = [1,3,2,8,4,9], fee = 2 — unlimited transactions, each sale pays the fee. Find the max profit..

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

time O(n)space O(1)step 1 / 12

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

132849

cashhold

-1

line 3

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

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap