You are given an array prices where prices[i] is the price of a stock on the i-th day.
Find the maximum profit with the constraint that after you sell your stock, you cannot buy on the next day (i.e., cooldown for one day).
You may complete as many transactions as you like.
Input: prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: Buy on day 1 (price=1), sell on day 2 (price=2), cooldown on day 3, buy on day 4 (price=0), sell on day 5 (price=2). Profit = 3.
Input: prices = [1]
Output: 0
We model three states: held (holding a stock), sold (just sold, entering cooldown), and rest (cooldown/idle, can buy next day).
- held = max(previous held, previous rest - price) — either keep holding or buy from rest state.
- sold = previous held + price — sell the stock you were holding.
- rest = max(previous rest, previous sold) — either stay resting or finish cooldown.
- Answer is max(sold, rest) at the end.
public class BestTimeBuySellStockWithCooldown {
public int maxProfit(int[] prices) {
int held = Integer.MIN_VALUE, sold = 0, rest = 0;
for (int price : prices) {
int prevHeld = held, prevSold = sold, prevRest = rest;
held = Math.max(prevHeld, prevRest - price);
sold = prevHeld + price;
rest = Math.max(prevRest, prevSold);
}
return Math.max(sold, rest);
}
}
Complexity Analysis:
Time complexity: O(n) — single pass through the array.
Space complexity: O(1) — three state variables.