1-D Dynamic Programming Buying and selling with states
533. Best Time to Buy and Sell Stock with Cooldown
You are given an array prices, where prices[i] is the price of one share on day i. You may buy and
sell as many times as you like, but you can hold at most one share at a time. So you must sell the share
you hold before you buy again.
After you sell, the next day is a cooldown: you cannot buy on that day. You may buy again the day after it. There is no cooldown after a buy.
Return the largest total profit you can make. The profit of one trade is the selling price minus the buying price. If no trade makes money, return 0.
Example 1
Input: prices = [1, 6, 8, 1, 5, 8]
12Explanation: Buy at 1 on day 0 and sell at 6 on day 1. Day 2 is the cooldown. Then buy at 1 on day 3 and sell at 8 on day 5. Selling at 8 on day 2 would put the cooldown on day 3 and lose the second chance to buy at 1.
Example 2
Input: prices = [9, 8, 6, 3]
0Explanation: The price only falls, so every trade loses money. Not trading gives 0.
Example 3
Input: prices = [0, 1000000000, 0, 1000000000]
1000000000Explanation: A sale on day 1 puts the cooldown on day 2, the other day with price 0. So only one of the two rises can be traded.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.