<p>You are given an integer 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, and an integer <code>k</code>.</p>

<p>Find the maximum profit you can achieve. You may complete at most <code>k</code> transactions: i.e. you may buy at most <code>k</code> times and sell at most <code>k</code> times.</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> k = 2, prices = [2,4,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
</pre>

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

<pre>
<strong>Input:</strong> k = 2, prices = [3,2,6,5,0,3]
<strong>Output:</strong> 7
<strong>Explanation:</strong> Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
</pre>

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

<ul>
	<li><code>1 &lt;= k &lt;= 100</code></li>
	<li><code>1 &lt;= prices.length &lt;= 1000</code></li>
	<li><code>0 &lt;= prices[i] &lt;= 1000</code></li>
</ul>

class Solution:  
        
    def maxProfit(self, k: int, prices: List[int]) -> int:
        '''
        we can't use the same algo as we did for k=2 because we may not have the full list to work with
        
        dp[i][j] represents max profit if buying and selling in prices[i:j]
        - can generate this in O(n^2) time
        
        then we have to find the best k
        - can't use binayr search cause it's not sorted
        
        iterate j from 1 to len(prices)
        - check dp[:j] + self.maxProfitHelper(k-1, prices[j:])
        - instead, we don't need dp here, we can find best price from i to j while we iterate throguh
        
        
        O(n^K) time
        O(k) space
        
        ----
        we can use memo/dp for self.maxProfitHelper(k-1, prices[j:])
        
        memo[(k, i)] where k is the number of parititons we can do and i is the index we are on (consdiering prices[i:])
        
        O(k*n * n) time, since it takes O(n) time to cmpute each one
        O(k*n) space
        
        ----
        reading solution
        an optimizaiton we can make is check if memo[k-1][prices[j-1]] exists, and is > than our 
        current prpofit, if it is than this result will be redundant and we can stop
        - will need to keep track of our current profit so far, that's easy
            - basically only call the function when the max_profit increases?
        worst case would still be the same tho if we get lot of dips and peaks in the array
        
        ----
        using solution but implmeneting myself
        
        dp[day_number][used_transaction_number][stock_holding_status] to represent our states, where stock_holding_status is a 0/1 number representing whether you hold the stock or not.

The value of dp[i][j][l] represents the best profit we can have at the end of the i-th day, with j remaining transactions to make and l stocks.

        dp[i][j][1] = max(dp[i-1][j+1][0] + 
        - oh okay, was confused but we don't need to know when we bought it because we subtract the 
        amount from our profit the moment we buy it, so just knowing when we sold it is sufficinet
        
        better than mine because don't need to iterate through the whole list to get the next state
        - next time try thinking from the opposite way
            - for eveyrthing not in terms of just the list, even number of transactions (go from 0 to k
            not k to 0)
        
        
        o(n*k) time
        O(k*n) space
        
        dp[0][0][0] = 0
        dp[0][0][1] = -prices[0]
        
        dp[i][j][0] means we don't have the stock after the ith day

        selling the stock (because we had the stock from previous day, not necessarily bought it on
        that day, we take the max profit so far with also having the stock on that day)

        dp[i][j][0] = dp[i-1][j-1][1] + prices[i]

        j being number of times we sold
        - we could say j being number of times we bought too, but then we might sell more than 
        what we actually have
            - we could also make each row 2k elements, and it repserents number of transactions
                - tho that would also be invalid because we might just sell 2*k times

        keep not having teh stock 
        dp[i][j][0] = dp[i-1][j][0]

        having the estock, either we had it form before or we buy it now, take whatever gives us
        the max profit currently ()
        dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])
        '''
        dp= []
        for i in range(len(prices)):
            row = []
            for j in range(k+1):
                row.append([-sys.maxsize,-sys.maxsize])
            dp.append(row)
        # dp = [[[0, -2], [-inf, -inf], [-inf, -inf]],[[0, -2], [-inf, -inf], [-inf, -inf]],[[-inf, -inf], [-inf, -inf], [-inf, -inf]]]
        dp[0][0][0] = 0
        dp[0][0][1] = -prices[0]
        for i in range(1, len(dp)):
            for j in range(len(dp[i])):
                dp[i][j][0] = dp[i-1][j][0]
                if j > 0:
                    dp[i][j][0] = max(dp[i-1][j-1][1] + prices[i], dp[i][j][0])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])
        
        highest = 0
        for j in range(len(dp[-1])):
            highest=max(dp[-1][j][0], highest) # highest swould never be holding a stock at the end
        return highest
                
'''
2
[2,4,1]
2
[3,2,6,5,0,3]
2
[2,4,1]
1
[3,2,6,5,0,3]

should be 7 still
3
[3,2,6,5,0,3,1,2]
should be 8 now
3
[3,2,6,5,0,3,1,2]


# dp = [[[0, -2], [-inf, -inf], [-inf, -inf]],[[-inf, -inf], [-inf, -inf], [-inf, -inf]],[[-inf, -inf], [-inf, -inf], [-inf, -inf]]]


'''
34394