730. Trades With Rest Days
A street vendor can trade a single collectible card whose market price for each day is listed in prices. The vendor holds at most one card at a time, so a card must be sold before another is bought, and buying and selling may be repeated as often as wanted. After selling a card, the vendor needs a rest and cannot buy anything on the very next day.
Return the largest total profit achievable over the whole period. The vendor may also do nothing at all, so the answer is never negative.
Aim for time O(n) and extra space O(1).
Example 1
- Input:
- prices = [12,4,15,9,20,6]
- Output:
- 16
- Explanation:
Buying at 4 and selling at 20 earns 16; selling at 15 instead would force a rest on the day priced 9, so the better follow-up trade is not available.
Example 2
- Input:
- prices = [9,7,5,3]
- Output:
- 0
- Explanation:
The price only falls, so any trade would lose money and the best profit is 0.
Constraints
1 ≤ prices.length ≤ 100000
0 ≤ prices[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)