Best Time to Buy and Sell Stock with Cooldown
Problem
Given prices[i], you may complete as many transactions as you want with the constraint that after selling you must rest one day before buying again. Return the maximum profit.
prices = [1, 2, 3, 0, 2]3def maxProfit(prices):
hold, sold, rest = float("-inf"), 0, 0
for p in prices:
prev_sold = sold
sold = hold + p
hold = max(hold, rest - p)
rest = max(rest, prev_sold)
return max(sold, rest)function maxProfit(prices) {
let hold = -Infinity, sold = 0, rest = 0;
for (const p of prices) {
const prevSold = sold;
sold = hold + p;
hold = Math.max(hold, rest - p);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}class Solution {
public int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE, 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 {
public:
int maxProfit(vector<int>& prices) {
int hold = INT_MIN, sold = 0, rest = 0;
for (int p : prices) {
int prevSold = sold;
sold = hold + p;
hold = max(hold, rest - p);
rest = max(rest, prevSold);
}
return max(sold, rest);
}
};Explanation
After every sell you must cooldown one day before buying again. We model this as a tiny state machine with three states and track the best profit reachable in each: hold (currently own a share), sold (just sold today), and rest (not holding and free to act).
Each day we recompute all three. sold = hold + p means selling today's share for price p. hold = max(hold, rest - p) means either keep holding or buy today (only allowed from rest, which guarantees the cooldown). rest = max(rest, prev_sold) lets yesterday's "sold" become today's "rest", enforcing the one-day wait.
We must use prev_sold (the previous day's value) because once we overwrite sold for today it no longer represents "sold yesterday".
The best final answer is max(sold, rest) — ending while still holding a share is never optimal.
Example: prices = [1,2,3,0,2]. Buy@1 sell@2 (+1), cooldown, buy@0 sell@2 (+2), total 3.