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]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

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

Solutions:
class Solution:

	def maxProfit(self, prices):
		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):
		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):
		if prices is None or len(prices) == 0:
			return 0
		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):
		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):
		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):
		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_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):
		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):
		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:
			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:
			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:
			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