Best profit when each trade pays a fee

Question

Given daily prices and a fixed fee charged on every completed round trip, you may buy and sell as often as you like (holding at most one share at a time). Return the maximum profit. Aim for O(n) time, O(1) space.

Accepted Answer

Run a two-state machine. On each day you are either holding a share or in cash, and you track the best achievable balance in each state: - cash, no share: either you stay in cash, or you sell today (collecting the price, minus the fee). - hold, one share: either you keep holding, or you buy today. Transitions per day at price p: 	ext{cash}' = \max(	ext{cash},\ 	ext{hold} + p - 	ext{fee}) \qquad 	ext{hold}' = \max(	ext{hold},\ 	ext{cash} - p). Charging the fee once, on the sell, is the clean choice; it means a round trip only happens when the gain clears the fee, so tiny wiggles are ign…

Best profit when each trade pays a fee

Your answer

More Coding questions