Trading With a Rest Day
Problem
Given the daily share prices prices, you may complete as many buy-sell trades as you like, holding at most one share at a time. After every sale, exchange rules force you to sit out the next day: you cannot buy on the day right after you sell.
Return the maximum total profit.
Example 1
- Input:
- prices = [2, 5, 1, 4, 6]
- Output:
- 5
Buy at 1 and sell at 6. Buying at 2, selling at 5 and then rebuying at 1 is not allowed: day 2 is the rest day.
Example 2
- Input:
- prices = [9, 7, 4]
- Output:
- 0
Example 3
- Input:
- prices = [1, 2, 3, 0, 2]
- Output:
- 3
Buy 1, sell 2, rest on the 3, buy at 0, sell at 2.
Constraints
- 1 ≤ prices.length ≤ 5000
- 0 ≤ prices[i] ≤ 1000
Hint
Show the first hint
Two states (holding / not holding) are no longer enough: 'not holding' splits into 'free to buy' and 'just sold'.
Walkthrough
How to approach it
01Clarify before coding
- Does the rest day apply only after selling? Yes, buying does not force a rest.
- Can I sell and buy on the same day? No, and the rest day forbids buying the next day too.
- Can I end while holding a share? You can, but it never helps, so the answer ignores that state.
02Brute force
Recursively try buy / sell / wait every day, remembering whether you hold a share and whether today is a rest day.
Cost: O(3^n) without memoisation.
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.