Best Time to Buy and Sell Stock with Cooldown
Medium · dynamic programming
The list prices gives the price of one share of a company on each day, in order.
You may trade as often as you like, but with these rules:
- you can hold at most one share at a time, so you must sell before you buy again;
- on one day you can do only one thing: buy, sell, or nothing;
- after you sell, you must skip the next day: you cannot buy on the day right after a sale.
Return the largest total profit you can make. If no trade makes money, return 0.
Examples
Example 1
Input: prices = [1, 2, 3, 0, 2]
Output: 3
Buy at 1 and sell at 2 (profit 1). Skip a day, then buy at 0 and sell at 2 (profit 2). Total 3.
Example 2
Input: prices = [5]
Output: 0
One day gives no chance to buy and sell.
Example 3
Input: prices = [1, 4, 2, 7]
Output: 6
Buy at 1 and sell at 7. Selling at 4 instead would force you to skip the day priced 2, leaving nothing worthwhile to buy afterwards.
Constraints
- 1 <= len(prices) <= 1000
- 0 <= prices[i] <= 1000