Best Time to Buy and Sell Stock with Transaction Fee
Max profit from unlimited trades where every completed transaction costs a flat fee.
Open on LeetCode ↗Intuition
The instinctive move is to subtract the fee whenever money changes hands, once on the buy and once on the sell. That double-charges every round trip and undercounts profit. The fee is per completed transaction, not per action, so charge it exactly once, conventionally when you sell, and leave the buy transition untouched. Once that's settled, this is otherwise the same two-state recurrence as unlimited-transaction stock trading: hold a share or be free of one, each a running max over what you did yesterday.
Approach
Two rolling states
hold tracks the best profit while owning a share; free tracks the best profit owning nothing. Initialize hold to -prices[0] (buy immediately) and free to 0.
Charge the fee once, on the sell
Each day, new_hold is the better of keeping yesterday's share or buying today out of yesterday's free. new_free is the better of staying free or selling today's held share, subtracting the fee only on that sell transition: hold + price - fee.
Answer is the final free state
Ending the timeline while still holding a share can never be optimal, since selling it (even after paying the fee) is only ever better or equal. The answer is free after the last day.
Solution & live demo
Edge cases
Every candidate sell value (hold + price - fee) stays below just staying free, so free never updates above 0 and the answer is 0.
hold becomes -prices[0] but free stays 0 since there is no second day to sell on; answer is 0.
The state machine naturally avoids paying the fee on every micro-uptick by only committing to a sell when hold + price - fee beats holding out for a later price.
Reduces exactly to the unlimited-transactions problem, since the sell transition becomes hold + price with no penalty.