Best Time to Buy and Sell Stock with Transaction Fee
Maximize profit from unlimited trades when every sale costs a fee, with a two-state dynamic program over days: holding a share or holding cash.
Problem Understanding
Best Time to Buy and Sell Stock with Transaction Fee: given daily prices and a fee, make as many transactions as you like, holding at most one share at a time, and paying fee for each one. Return the maximum profit.
Examples: [1,3,2,8,4,9], fee 2 → 8 (buy 1, sell 8; buy 4, sell 9); [1,3,7,5,10,3], fee 3 → 6.
The Intuition: Two Running Bests
This is the state-machine dynamic programming from Stock with Cooldown, with one state fewer:
- cash: best profit ending the day without a share. Either stay out, or sell today:
hold + price − fee. - hold: best profit ending the day with a share. Either keep it, or buy today:
cash − price. - Answer: cash on the last day.
Without a fee this reduces to Best Time to Buy and Sell Stock II, where taking every rise is optimal.
Interactive Walkthrough
FEE 2 PER SALE
DAY 0
day
0
1
2
3
4
5
price
cash
hold
day
0
profit
:
Day 0, price 1: cash = 0 (do nothing), hold = −1 (buy today). Each sale costs a fee of 2
Next
Day 1, price 3: cash = max(0, sell -1 + 3 − 2 = 0) = 0; hold = max(-1, buy 0 − 3 = -3) = -1
prices
fee
Each column is a day; the day being computed is solid and yesterday's states are tinted. At the end the winning path through the states turns green and the buys and sells are labeled. Try Fee wins to see a dip ignored.
Dry Run Table
Input: [1,3,2,8,4,9], fee 2.
| Day | Price | cash | hold |
|---|---|---|---|
| 0 | 1 | 0 | −1 |
| 1 | 3 | 0 | −1 |
| 2 | 2 | 0 | −1 |
| 3 | 8 | 5 | −1 |
| 4 | 4 | 5 | 1 |
| 5 | 9 | 8 | 1 |
Answer: 8 (buy at 1, sell at 8; buy at 4, sell at 9).
The Solution Template
Two variables updated once per day.
Best Time to Buy and Sell Stock with Transaction Fee Code
1var maxProfit = function(prices, fee) {2 let cash = 0, hold = -prices[0];3 for (let i = 1; i < prices.length; i++) {4 const prevCash = cash;5 cash = Math.max(cash, hold + prices[i] - fee);6 hold = Math.max(hold, prevCash - prices[i]);7 }8 return cash;9};
Edge Cases & Common Mistakes
- One day: no sale possible; the answer is 0.
- Fee larger than every rise: never trade; cash stays 0.
- Charging the fee on both buy and sell: that is twice per trade.
- Greedy on every rise: pays the fee on each small swing; use the DP.
- Returning max(cash, hold): hold is never larger than cash at the end, but returning cash is the honest answer.
Summary
Keep the best profit holding cash and holding a share; each day either keep the state or switch, paying the fee on each sale. Return cash. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet