Learning On the Way

309. Best Time to Buy and Sell Stock with Cooldown

State Machine Method

class Solution(object): 
    def maxProfit(self, prices): 
        """ 
        :type prices: List[int] 
        :rtype: int 
        """ 
        sold, held, reset = float('-inf'), float('-inf'), 0 
        for price in prices: 
            # Alternative: the calculation is done in parallel. 
            # Therefore no need to keep temporary variables 
            #sold, held, reset = held + price, max(held, reset-price), max(reset, sold) 
            pre_sold = sold 
            sold = held + price 
            held = max(held, reset - price) 
            reset = max(reset, pre_sold) 
        return max(sold, reset)

Dynamic Programming

class Solution(object): 
    def maxProfit(self, prices): 
        """ 
        :type prices: List[int] 
        :rtype: int 
        """ 
        L = len(prices) 
        # padding the array with additional zero to simply the logic 
        MP = [0] * (L + 2) 
        for i in range(L-1, -1, -1): 
            C1 = 0 
            # Case 1). buy and sell the stock 
            for sell in range(i + 1, L): 
                profit = (prices[sell] - prices[i]) + MP[sell + 2] 
                C1 = max(profit, C1) 
            # Case 2). do no transaction with the stock p[i] 
            C2 = MP[i + 1] 
            # sum up two cases 
            MP[i] = max(C1, C2) 
        return MP[0]