<p>You are given an array <code>prices</code> where <code>prices[i]</code> is the price of a given stock on the <code>i<sup>th</sup></code> day.</p>

<p>Find the maximum profit you can achieve. You may complete <strong>at most two transactions</strong>.</p>

<p><strong>Note:</strong> You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> prices = [3,3,5,0,0,3,1,4]
<strong>Output:</strong> 6
<strong>Explanation:</strong> 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.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> prices = [1,2,3,4,5]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= prices.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= prices[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def recursion(self , day , trans , canBuy , prices ):

        if day == len(prices):
            return 0
        if trans == 0:
            return 0

        if canBuy:
            buy = -prices[day] + self.recursion(day + 1 , trans , False , prices)
            notBuy = 0 + self.recursion(day + 1 , trans , True , prices)
            return max(buy , notBuy)
        else:
            sell = +prices[day] + self.recursion(day + 1 , trans - 1 , True , prices)
            notSell = 0 +self.recursion(day + 1 , trans , False , prices)
            return max(sell , notSell)
        

    def memorization(self , day , trans , canBuy , prices , dp ):
        if trans == 0:
            return 0
        if day == len(prices):
            return 0
        
        if dp[day][trans][canBuy] != -1:
            return dp[day][trans][canBuy]
        
        if canBuy:
            buy = -prices[day] + self.memorization(day + 1 , trans , False , prices , dp)
            notBuy = 0 + self.memorization(day + 1 , trans , True , prices , dp)
            dp[day][trans][canBuy] = max(buy , notBuy)
        else:
            sell = +prices[day] + self.memorization(day + 1 , trans -1  , True , prices , dp)
            notSell = 0 + self.memorization(day + 1 , trans , False , prices , dp)
            dp[day][trans][canBuy] = max(sell , notSell)
        
        return dp[day][trans][canBuy]

    def tabulation(self , prices):
        lenPrices = len(prices)
        ## we actually need to have 
        # day from 0 to n   , to len as n + 1
        # trans as 0  , 1 , 2  , so len as 3
        ## canBuy as True / False , so len as 2

        dp  =  [ [ [ 0  for _ in range(2)] for i in range(3)] for j in range(lenPrices + 1)]
        ## as everything is for 0 , we doesn't bother 
        #3 about base base 
        #3 recursion from 0 to n-1 
        ## True       0th index for True , 1th Index for False 
        ##  Transation is start from 0 
        ## we access everyting at day 0 , trans as 2 m True

        #3 in recursion it starts from 0th day to n-1 th day 
        ## so here in dp it shoudl start from n-1th day 

        for day in range(lenPrices - 1 , -1 , -1):
            for trans in range(1 ,3): ## varies frmo 1 , 2 
                for canBuy in range(2): 
                    if canBuy == 0:   ## True   ## Buy
                        buy = -prices[day] + dp[day + 1][trans][1]
                        notBuy = 0 + dp[day + 1][trans][0]
                        dp[day][trans][canBuy] = max(buy , notBuy)
                    elif canBuy == 1:  ## False   ## sell
                        sell = +prices[day] + dp[day + 1][trans - 1][0]
                        notSell = 0 + dp[day  + 1][trans][1]
                        dp[day][trans][canBuy] = max(sell , notSell)
        
        return dp[0][2][0]



    def maxProfit(self, prices: List[int]) -> int:
        ## there is 1 ways to solve this problem
        ## one is extension of previouse problem like 
        ## maintain the another varible , to tell , wheather it reaches limit 
        ## a transactions is said to done for 1 buy and sell 
        ## so change the trans varble at sell , 

        ## as it was from starting 
        ## 0th Day , translimit as 2 , canBuy as True

        lenPrices = len(prices)

        # res = self.recursion(0 , 2 , True , prices)
        # return res

        ## for memorization
        ## day    0 to n -1 days   as n len
        ## transatin  0 to 2       as 3 len
        ## canBuy True , False     as 2 len

        dp = [[[-1 for _ in range(2)] for i in range(3) ] for j in range(lenPrices)]
        res = self.memorization(0 , 2 , True , prices , dp)
        return res

        # res = self.tabulation(prices)
        # return res


        
        
101471