Trading With a Commission
Problem
You track the daily price of one share in prices. You may hold at most one share at a time, and you may buy and sell as many times as you like, but the broker charges a flat fee every time you sell.
Return the maximum total profit you can make. Buying and selling on the same day gains nothing, so it never helps.
Example 1
- Input:
- prices = [1, 4, 2, 8, 3, 9], fee = 2
- Output:
- 9
Buy at 1, sell at 8 (gain 7 - 2 = 5), buy at 3, sell at 9 (gain 6 - 2 = 4). Selling at 4 first would waste a fee.
Example 2
- Input:
- prices = [5, 4, 3, 2], fee = 1
- Output:
- 0
Prices only fall, so the best plan is not to trade.
Constraints
- 1 ≤ prices.length ≤ 10^5
- 1 ≤ prices[i] ≤ 5 · 10^4
- 0 ≤ fee ≤ 5 · 10^4
Hint
Show the first hint
At the end of each day you are in one of two situations: holding a share, or not.
Walkthrough
How to approach it
01Clarify before coding
- Is the fee charged per completed trade? Yes, once per sell (equivalently once per buy-sell pair).
- Can I hold more than one share? No, at most one.
- Can the profit be negative? No: not trading is always allowed, so the answer is at least 0.
02Brute force
Recursively decide on each day whether to buy, sell or wait, given whether you currently hold a share.
Cost: O(2^n) without memoisation: each day branches.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.