309. Best Time to Buy and Sell Stock with Cooldown - cocoder39/coco39_LC GitHub Wiki

309. Best Time to Buy and Sell Stock with Cooldown

2020 Notes:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        
        sold = [0] * n
        reset = [0] * n
        hold = [0] * n
        hold[0] = -prices[0]
                
        for i in range(1, n):
            sold[i] = hold[i-1] + prices[i]
            hold[i] = max(hold[i-1], reset[i-1] - prices[i])
            reset[i] = max(reset[i-1], sold[i-1])
            
        return max(sold[-1], hold[-1], reset[-1])

======================================================================================================

three states: initial state is rest, from rest, you can go to buy state if there is a buy transaction, or stay at rest. if you are at buy state, you can go to sell state if there is a sell transaction, or stay at sell. if you are at sell state, your next state has to be rest.

thus, rest state comes from rest state or sell state. buy state comes from buy state or rest state. sell state comes from buy state

int sz = prices.size();
        if(sz == 0){
            return 0;
        }
        
        vector<int> rest(sz); //rest[i] is the maxProfit of a sequence where the last one is no tranaction by day i
        vector<int> buy(sz); //buy[i] is the maxProfit for a sequence where the last one is buy by day i
        vector<int> sell(sz); //sell[i] is the maxProfit a sequence where the last one is sell by day i
        rest[0] = 0;
        buy[0] = -prices[0];
        sell[0] = 0; // ensure no sell on first day
        
        for(int i = 1; i < sz; i++){
            rest[i] = max(rest[i - 1], sell[i - 1]); 
            buy[i] = max(buy[i - 1], rest[i - 1] - prices[i]);
            sell[i] = buy[i - 1] + prices[i];
        }
        return max(buy[sz - 1], max(sell[sz - 1], rest[sz - 1]));
    }

the memory can be further optimized to O(1)

int maxProfit(vector<int>& prices) {
        int rest = 0;
        int buy = INT_MIN;
        int sell = 0; 
        
        for(int i = 0; i < prices.size(); i++){
            int buy_pre = buy;
            int sell_pre = sell;
            int rest_pre = rest;
            
            rest = max(rest_pre, sell_pre); 
            buy = max(buy_pre, rest_pre - prices[i]);
            sell = buy_pre + prices[i];
        }
        return max(buy, max(sell, rest));
    }
⚠️ **GitHub.com Fallback** ⚠️