Best Time to Buy and Sell Stock with Transaction Fee
Medium · Dynamic Programming · Array · Dynamic Programming · Greedy
Problem
You are given prices, where prices[i] is a stock's price on day i, and a whole number fee.
You may make as many trades as you like, but you hold at most one share at a time (sell before you buy again), and each complete buy-and-sell pays fee once.
Return the largest profit you can make. Making no trades at all earns 0.
Examples
Input: prices = [2,8,4,9], fee = 2 Output: 7
Two trades, 2 → 8 and 4 → 9, earn 6 + 5 - 2 · 2 = 7. A single trade 2 → 9 earns only 7 - 2 = 5.
Input: prices = [5,4,3], fee = 1 Output: 0
Prices only fall, so the best plan is not to trade.
Constraints
- 1 <= len(prices) <= 5 · 10^4
- 1 <= prices[i] < 5 · 10^4
- 0 <= fee < 5 · 10^4
Approaches
- Best profit by each day, trying every last trade — time O(n²), space O(n)
Follow-up
What if you may make at most k trades? Then the two states split per trade count: hold[t] and cash[t] for t = 1..k, giving O(n · k). See the use case "At most k trades, each paying a fee".
Related problems
Start free on Cariara · Coding problems · System design studio
