Best Time to Buy And Sell Stock With Cooldown
The drill: Buy and sell a single share as many times as you like across these daily prices to maximize profit — but after every sell you must sit out one full day before buying again.
A sequence of daily stock prices arrives, and the task is to buy and sell a single share of stock as many times as helpful to maximize total profit.
Only one share can be held at a time — a new share can't be bought while already holding one, and a sale has to happen before buying again. After any sale, though, a full day of cooldown must pass before the next buy is allowed.
There's no requirement to actually trade; sitting out entirely and taking zero profit is always a valid, if unhelpful, option. The output is the maximum profit reachable under these rules.
- prices are non-negative, and the list can be short or empty
- at most one share is held at any moment
- one full day of cooldown is required after every sell before the next buy
- not trading at all is valid, giving a baseline profit of zero
HINT 1 THE NUDGE
At any point you're in exactly one of three situations: holding a share, freshly sold and resting, or free to buy. What determines the best outcome from here in each case?
HINT 2 THE STRUCTURE
Today's 'holding' can only descend from yesterday's 'holding' (do nothing) or yesterday's 'free, no cooldown' (buy today) — it can never come straight from yesterday's 'just sold'.
HINT 3 ONE STEP FROM THE ANSWER
Track three running maxima across the days: hold, sold-today, and rest (free with no cooldown). hold = max(hold, rest − price); sold = hold_prev + price; rest = max(rest, sold_prev). Answer is max(sold, rest) at the end.
Day0, price2. Buying now costs 2, so hold starts at -2; nothing sold yet, so sold and rest sit at 0.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
hold = -prices[0]
sold = 0
rest = 0
for price in prices[1:]:
hold, sold, rest = max(hold, rest - price), hold + price, max(rest, sold)
return max(sold, rest)class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
def dfs(i, holding, cooldown):
if i == n:
return 0
best = dfs(i + 1, holding, False) # do nothing today
if holding:
best = max(best, prices[i] + dfs(i + 1, False, True)) # sell
elif not cooldown:
best = max(best, -prices[i] + dfs(i + 1, True, False)) # buy
return best
return dfs(0, False, False)class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int hold = -prices[0];
int sold = 0;
int rest = 0;
for (int i = 1; i < prices.length; i++) {
int price = prices[i];
int newHold = Math.max(hold, rest - price);
int newSold = hold + price;
int newRest = Math.max(rest, sold);
hold = newHold;
sold = newSold;
rest = newRest;
}
return Math.max(sold, rest);
}
}class Solution {
private int[] prices;
private int n;
public int maxProfit(int[] prices) {
this.prices = prices;
n = prices.length;
return dfs(0, false, false);
}
private int dfs(int i, boolean holding, boolean cooldown) {
if (i == n) {
return 0;
}
int best = dfs(i + 1, holding, false);
if (holding) {
best = Math.max(best, prices[i] + dfs(i + 1, false, true));
} else if (!cooldown) {
best = Math.max(best, -prices[i] + dfs(i + 1, true, false));
}
return best;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED