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 at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:


Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:


Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.


Example 3:


Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

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
         """
         tmax_profit = 0
         rmax_profits = [0] * len(prices)
         rmax = -1
         for ii in range(len(prices)-2, -1, -1):
             if (prices[rmax] - prices[ii] > rmax_profits[ii+1]):
                 rmax_profits[ii] = prices[rmax] - prices[ii]
             else:
                 rmax_profits[ii] = rmax_profits[ii+1]
             if prices[ii] > prices[rmax]:
                 rmax = ii
         #print("rmax profit = {}".format(rmax_profits))
         lmin = 0
         lmax_profit = 0
         for ii in range(1, len(prices)):
             profit = prices[ii]-prices[lmin]
             if  profit > lmax_profit:
                 lmax_profit = profit
             if prices[ii] < prices[lmin]:
                 lmin = ii
             tprofit = lmax_profit
             if ii < len(prices)-1:
                 tprofit += rmax_profits[ii+1]
             #print("ii = {}, rmax_profit = {}, lmax_profit = {}, tprofit = {}".format(ii, rmax_profits[ii], lmax_profit, tprofit))
             if tprofit > tmax_profit:
                 tmax_profit = tprofit
         return tmax_profit if tmax_profit>0 else 0        

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         
         n = len(prices)
         
         sell1 = 0
         sell2 = 0
         hold1 = -prices[0]
         hold2 = -prices[0]
         
         for i in range(1, n):
             sell2 = max(prices[i] + hold2, sell2)
             hold2 = max(sell1 - prices[i], hold2)
             sell1 = max(prices[i] + hold1, sell1)
             hold1 = max(-prices[i], hold1)
             
             
             
             #sell1[i] = max(sell1[i-1], prices[i] + hold1[i-1])
             #hold1[i] = max(hold1[i-1],  -prices[i])
             #sell2[i] = max(prices[i] + hold2[i-1], sell2[i-1] )
             #hold2[i] = max(sell1[i-1] - prices[i], hold2[i-1])
             
         return sell2
             
 
 


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         #一天可以买卖2次
         import sys
         min_v=-sys.maxsize
         buy1,buy2=min_v,min_v
         sell1,sell2=0,0
         for i in prices:
             buy1=max(buy1,-i)
             #卖，分为本次不卖 或卖
             sell1=max(sell1,buy1+i)
             
             buy2=max(buy2,sell1-i)
             #卖，分为本次不卖 或卖
             sell2=max(sell2,buy2+i)
         return sell2


class Solution:
     def maxProfit(self, prices, k = 2):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         
         s1 = s2 = 0
         b1 = b2 = -1000000000
         
         for p in prices:
             b1 = max(b1, -p)
             s1 = max(s1, b1 + p)
             b2 = max(b2, s1 - p)
             s2 = max(s2, b2 + p)
         
         return s2


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         sell_date = [0] * len(prices)
         min_price = prices[0]
         for i in range(1, len(prices)):
             sell_date[i] = max(sell_date[i - 1], prices[i] - min_price)
             min_price = min(prices[i], min_price)
         
         max_price, profit = prices[-1], 0
         for i in range(len(prices) - 1, 0, -1):
             profit = max(profit, max_price - prices[i] + sell_date[i])
             max_price = max(max_price, prices[i])
         
         return profit

class Solution:
     def maxProfit(self, prices):
         length=len(prices)
         if length==0: return 0
         f1=[0 for i in range(length)]
         f2=[0 for i in range(length)]
         
         minV=prices[0]; f1[0]=0
         for i in range(1,length):
             minV=min(minV, prices[i])
             f1[i]=max(f1[i-1],prices[i]-minV)
             
         maxV=prices[length-1]; f2[length-1]=0
         for i in range(length-2,-1,-1):
             maxV=max(maxV,prices[i])
             f2[i]=max(f2[i+1],maxV-prices[i])
 
         res=0
         for i in range(length):
             if f1[i]+f2[i]>res: 
                 res=f1[i]+f2[i]
                 
         return res
                     
             
         
         


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if len(prices)<2:
             return 0
         buy = []
         sell = []
         for i in range(2):
             buy.append(-float("inf"))
             sell.append(-float("inf"))
         
         for i in prices:
             for j in range(2):
                 if j== 0:
                     buy[j] = max(buy[j], -i)
                     sell[j] = max(sell[j], i+buy[j])
                 else:
                     buy[j] = max(buy[j], sell[j-1]-i)
                     sell[j] = max(sell[j], i+buy[j])
         
         return sell[-1]
         


class Solution:
     def maxProfit(self,prices):
         k = 2
         profit = []
         n = len(prices)
         if n < 2:
             return 0
 
         for i in range(k+1):
             profit.append([])
             for j in range(n):
                 profit[i].append(0)
 
         for i in range(1,k+1):
             tmpMax = profit[i-1][0] - prices[0]
             for j in range(n):
                 profit[i][j] = max(profit[i][j-1], prices[j] + tmpMax)
                 tmpMax = max(tmpMax,profit[i-1][j] - prices[j])
         return profit[k][n-1]
 
 
 


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         
         n = len(prices)
         
         sell1 = n * [0]
         hold1 = n * [0]
         sell2 = n * [0]
         hold2 = n * [0]
         
         hold1[0] = hold2[0] = -prices[0]
         
         for i in range(1, n):
             sell1[i] = max(sell1[i-1], prices[i] + hold1[i-1])
             hold1[i] = max(hold1[i-1],  -prices[i])
             sell2[i] = max(prices[i] + hold2[i-1], sell2[i-1] )
             hold2[i] = max(sell1[i-1] - prices[i], hold2[i-1])
             
         return sell2[n-1]
             


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         left2right = [0] * len(prices)
         right2left = [0] * len(prices)
         dp = prices[:]
         
         max_profit = 0
         for i in range(1, len(prices)):
             dp[i] = min(dp[i - 1], prices[i])
             left2right[i] = max(left2right[i], prices[i] - dp[i])
             max_profit = max(max_profit, prices[i] - dp[i])
         
         dp = prices[:]
         for i in reversed(list(range(len(prices) - 1))):
             dp[i] = max(dp[i + 1], prices[i])
             right2left[i] = max(right2left[i + 1], dp[i] - prices[i])
             
         print(right2left)
         
         for i in range(len(prices) - 1):
             max_profit = max(max_profit, left2right[i] + right2left[i + 1])
         
         return max_profit


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:return 0
         times,n = 2, len(prices)
         dp = [[0 for j in range(n)] for i in range(times)]
         buy_in = -prices[0]
         for i in range(1,n):
             dp[0][i] = max(dp[0][i-1], prices[i] + buy_in)
             buy_in = max(buy_in, -prices[i])
             
             
         
         for k in range(1,times):
             buy_in = -prices[0]
             for j in range(1,n):
                 dp[k][j] = max(buy_in + prices[j], dp[k][j-1])
                 buy_in = max(buy_in, dp[k-1][j] - prices[j])
         return dp[-1][-1]

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         buy1, sell1, buy2, sell2 = -prices[0], 0, -prices[0], 0
         for p in prices:
             buy1 = max(buy1, -p)
             sell1 = max(sell1, buy1 + p)
             buy2 = max(buy2, sell1 - p)
             sell2 = max(sell2, buy2 + p)
         return sell2