Best Time Buy/Sell Stock Cooldown — State DP
Sanjeev SharmaAdvertisement
Problem
Unlimited transactions, but after selling must rest 1 day (cooldown) before buying again.
Approach — 3-State DP
States: hold (holding stock), sold (just sold, cooldown), rest (not holding, can buy).
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def maxProfit(self, prices: list[int]) -> 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)
C++
class Solution {
public:
int maxProfit(vector<int>& p){
int hold=INT_MIN,sold=0,rest=0;
for(int x:p){
int nh=max(hold,rest-x),ns=hold+x,nr=max(rest,sold);
hold=nh;sold=ns;rest=nr;
}
return max(sold,rest);
}
};
Complexity
- Time: O(n) | Space: O(1)
Advertisement
