O(n) O(1)
Intuition
Each day you are in one of three states: holding a share, just sold (must cool down), or resting (free to buy). Track the best profit for each state and roll them forward.
Explanation
Three states
- hold — best profit while owning a share.
- sold — best profit having just sold today (tomorrow is a forced cooldown).
- rest — best profit while holding nothing and free to buy.
Transitions (day i)
new_sold = hold + price # sell today
new_hold = max(hold, rest - price) # keep holding, or buy today (only from rest)
new_rest = max(rest, sold) # keep resting, or the cooldown after a sale ends
Start: hold = -prices[0], sold = 0, rest = 0. The answer is max(sold, rest) — you never want to end still holding.
Worked example
prices = [1,2,3,0,2]: buy@1, sell@3 (+2), cooldown, buy@0, sell@2 (+2) → net 3.
Complexity
- Time: O(n).
- Space: O(1) — three rolling variables.
Implementation
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 prevSold = sold;
sold = hold + prices[i];
hold = Math.max(hold, rest - prices[i]);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}
}