#714
Best Time to Buy and Sell Stock with Transaction Fee
Medium State machine DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Trade as often as you like (one share at a time), paying a fee on every sale. Maximise profit.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: unlimited trades with a fee per sale.
Why this works: two states: holding a share or holding cash; pay the fee when selling.
Example: [1, 3, 2, 8, 4, 9], fee 2
buy 1 sell 8 (+5), buy 4 sell 9 (+3) → 8✦Hints open one at a time
Two states per day: holding a share or not.
cash = max(cash, hold + price − fee); hold = max(hold, cash − price).
↗Approach
Roll the two states through the days. Using the new cash when updating hold is safe here (it amounts to selling and rebuying on the same day, which never helps).
</>Solution (Java)
class Solution {
public int maxProfit(int[] prices, int fee) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
cash = Math.max(cash, hold + prices[i] - fee); // sell (pay fee)
hold = Math.max(hold, cash - prices[i]); // buy
}
return cash;
}
}!Common mistake
Charging the fee on both buy and sell.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon