Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:


       You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
       After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)


Example:


Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Difficulty: interview

Starter code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        

Solutions:
class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         n = len(prices)
         
         if n < 2: return 0
         
         sells = [0] * n
         buys = [0] * n
         
         buys[0] = -prices[0]
         
         for i in range(1, n):
             sells[i] = max(sells[i-1], buys[i-1] + prices[i])
             buys[i] = max(buys[i-1], (sells[i-2] if i > 1 else 0) - prices[i])
             
         return sells[n-1]

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         sell = hold = 0
         buy = -prices[0]
         
         for i in range(1, len(prices)):
             
             sell, hold, buy = max(buy + prices[i], 0), max(hold, sell), max(hold-prices[i], buy)
             
         return max(sell, hold)

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if prices is None or len(prices) == 0:
             return 0 
         # 0 for buy 1 for sell 2 for break
         dp = [[-9999999]*len(prices) for _ in range(3)]
         dp[0][0], dp[1][0], dp[2][0] = -prices[0], 0, 0
         for i in range(1, len(prices)):
             dp[0][i] = max(dp[0][i-1], dp[2][i-1] - prices[i])
             dp[1][i] = max(dp[0][i-1] + prices[i], dp[1][i-1])
             dp[2][i] = max(dp[2][i-1], dp[0][i-1], dp[1][i-1])
         return max(dp[1][-1], dp[2][-1])
             
                          


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         n = len(prices)
         if not n:
             return 0
         buys = [None] * n
         sells = [None] * n
         sells[0], buys[0] = 0, -prices[0]
         for x in range(1, n):
             delta = prices[x] - prices[x - 1]
             sells[x] = max(buys[x - 1] + prices[x], sells[x - 1] + delta)
             buys[x] = max(buys[x - 1] - delta, sells[x - 2] - prices[x] if x > 1 else -9999)
         return max(sells)


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         n = len(prices)
         if n < 2:
             return 0
 
         buy, sell = [0]*n, [0]*n
         buy[0], buy[1] = -prices[0], -min(prices[0:2])
         sell[1] = max(0, buy[0] + prices[1])
         for i in range(2, n):
             sell[i] = max(sell[i-1], buy[i-1] + prices[i])
             buy[i] = max(buy[i-1], sell[i-2] - prices[i])
 
         return sell[-1]        

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices or len(prices) == 1:
             return 0
         valid_status = [0, [prices[0], -prices[0]], 0]
         for t in range(1, len(prices)):
             valid_status[1][0] = prices[t]
             # cool down status
             cool_down_temp = sum(valid_status[1])
             if valid_status[0] > sum(valid_status[1]):
                 valid_status[1] = [prices[t], valid_status[0] - prices[t]]
             if valid_status[2] > valid_status[0]:
                 valid_status[0] = valid_status[2]
             valid_status[2] = cool_down_temp
         return max(valid_status[0], valid_status[2])

class Solution:
     def maxProfit(self, prices):
         if not prices:
             return 0
         max_buy = [0]*len(prices)
         max_sell = [0]*len(prices)
         max_rest = [0]*len(prices)
 
         max_buy[0] = -prices[0]
         max_sell[0] = 0
         max_rest[0] = 0
 
         for i in range(1, len(prices)):
             max_buy[i] = max(max_rest[i-1] - prices[i], max_buy[i-1])
             max_sell[i] = max(max_buy[i-1] + prices[i], max_sell[i-1])
             max_rest[i] = max(max_sell[i-1], max_rest[i-1])
                 
         return max(max_buy[-1], max_sell[-1], max_rest[-1])


class Solution:
     def maxProfit(self, prices):
         if not prices:
             return 0
         stock = -prices[0]
         noStock = 0
         noStockSell = 0
         
         for idx in range(len(prices)):
             price = prices[idx]
             print(noStock, stock, noStockSell)
             noStock, stock, noStockSell = [max(price + stock, noStock), max(noStockSell - price, stock), noStock]
               
         return noStock

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
 
         free = 0
         have = cool = float("-inf")
         for p in prices:
             free, have, cool = max(free, cool), max(have, free - p), have + p
         return max(free, cool)


class Solution:
     def maxProfit(self,prices):
         if not prices:
             return 0
         prices.insert(0,0)
         prices.insert(0,0)
         buy=[0]*len(prices)
         sell=[0]*len(prices)
         buy[2]=-prices[2]
     
         for i in range(3,len(prices)):
             buy[i]=max(sell[i-2]-prices[i],buy[i-1])
             sell[i]=max(buy[i-1]+prices[i],sell[i-1])
         return sell[-1]
                     
                     
                     


class Solution:
     def maxProfit(self,prices):
         if not prices:
             return 0
         prices.insert(0,0)
         prices.insert(0,0)
         buy=[0]*len(prices)
         sell=[0]*len(prices)
         buy[2]=-prices[2]
     
         for i in range(3,len(prices)):
             buy[i]=max(sell[i-2]-prices[i],buy[i-1])
             sell[i]=max(buy[i-1]+prices[i],sell[i-1])
         return sell[-1]
                     
                     
                     


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         return self.max_profit_rec(prices, {}, 0, 0)
     
     def max_profit_rec(self, prices, memo, idx, state):
         if idx >= len(prices): return 0
         if (idx, state) in memo: return memo[(idx, state)]
         memo[(idx, state)] = 0
         if state == 0:
             # can buy or ignore
             memo[(idx, state)] = max(self.max_profit_rec(prices, memo, idx+1, 1) - prices[idx], self.max_profit_rec(prices, memo, idx+1, 0))
         elif state == 1:
             # can sell or ignore
             memo[(idx, state)] = max(self.max_profit_rec(prices, memo, idx+1, 2) + prices[idx], self.max_profit_rec(prices, memo, idx+1, 1))
         else:
             # cooldown: must ignore
             memo[(idx, state)] = self.max_profit_rec(prices, memo, idx+1, 0)
         return memo[(idx, state)]


class Solution:
     def maxProfit(self, prices):
         
         if len(prices) < 2:
             return 0
         
         prevSell,sell,prevBuy,buy = 0,0,0,-prices[0]
         
         for price in prices:
             prevBuy = buy
             buy = max(prevBuy,prevSell-price)
             prevSell = sell
             sell = max(prevSell,prevBuy+price)
 
         return sell
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             
             


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         free=0
         have,cool=float('-inf'),float('-inf')
         for p in prices:
             free,have,cool=max(free,cool),max(free-p,have),have+p
         return max(free,cool)