Unlimited Trades
Problem
prices[i] is the price of a share on day i. You may hold at most one share at a time, but you may buy and sell as many times as you like. Selling and buying again on the same day is allowed.
Return the maximum total profit.
Example 1
- Input:
- prices = [7, 1, 5, 3, 6, 4]
- Output:
- 7
Buy at 1, sell at 5 (+4); buy at 3, sell at 6 (+3).
Example 2
- Input:
- prices = [1, 2, 3, 4, 5]
- Output:
- 4
Buy on day 0 and sell on day 4.
Example 3
- Input:
- prices = [7, 6, 4, 3, 1]
- Output:
- 0
Constraints
- 1 ≤ prices.length ≤ 3·10^4
- 0 ≤ prices[i] ≤ 10^4
Hint
Show the first hint
At the end of each day you are in one of two situations. Which?
Walkthrough
How to approach it
01Clarify before coding
- Can I hold two shares? No, at most one at a time.
- Is there a fee or a waiting period? No, trades are free and immediate.
- Must I end without a share? Ending with one is never better, so the answer is the 'free' state.
02Brute force
Recursively decide on every day: do nothing, buy (if free) or sell (if holding). Memoising on (day, holding) gives a 2n-state DP.
Cost: Without memo: O(2ⁿ). With memo: O(n) time and O(n) space plus deep recursion.
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.