Best Time to Buy and Sell Stock with Cooldown
You're given an array prices where prices[i] is a stock's price on day i. You may complete as many transactions as you like, but you can hold at most one share at a time, and after you sell you must wait one day before buying again. Return the maximum profit you can make.
Examples
prices = [2,5,1,4] returns 3
Selling at 5 on day 1 puts day 2 in cooldown, so the dip to 1 can't be bought. One trade of 3 is the best, either 2 to 5 or 1 to 4.
prices = [1,5,0,0,6] returns 10
Buy at 1 and sell at 5, rest on day 2, buy at 0 on day 3, and sell at 6 for 4 + 6 = 10.
prices = [6] returns 0
With one day there is nothing to trade.
Constraints
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
Hints
On any day, what situations can you be in, and which of them allow you to buy?
Use a small state machine with three states (holding, just sold, and resting), and keep the best profit for each as a DP over days.
Each day, compute newHold = max(hold, rest - p), newSold = hold + p, and newRest = max(rest, sold) from the old values. Return max(sold, rest) at the end.
Drill This: Your Approach First
Approach
Model each day as one of three states and track the best profit in each. hold: you own a share. sold: you sold today, so tomorrow is a cooldown. rest: you own nothing and are free to buy. The transitions are hold = max(hold, rest - price), sold = hold + price, and rest = max(rest, sold), all computed from the previous day's values. Start with hold = -infinity, sold = 0, and rest = 0, and return max(sold, rest). O(n) time, O(1) space.
Time
O(n)
Space
O(1)
Pitfall
Solutions
class Solution {
public int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE / 2, sold = 0, rest = 0;
for (int p : prices) {
int prevSold = sold;
sold = hold + p;
hold = Math.max(hold, rest - p);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}
}class Solution:
def maxProfit(self, prices) -> int:
hold, sold, rest = float("-inf"), 0, 0
for p in prices:
hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
return max(sold, rest)