<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 __init__(self):
        self.cache = {}
        self.used = 0
    def maxProfit(self, k: int, prices):
        if k == 0:
            return 0
        if len(prices) <= 1:
            return 0
        key = str(k) + "," + str(len(prices))
        if key in self.cache:
            self.used += 1
            return self.cache[key]

        max_profit = 0

        for i in range(1):
            # max_gain = 0
            # j = i+1
            # higher_found = False
            # idx =-1
            # while j < len(prices):
            #     if not higher_found and prices[j] - prices[i] > max_gain:
            #         max_gain = prices[j]-prices[i]
            #         idx = j
            #         higher_found = True
            #
            #     elif higher_found:
            #         if prices[j] < prices[j-1]:
            #             profits.append(prices[j-1]-prices[i] + self.maxProfit(min(k-1, len(prices[j:])//2), prices[j:]))
            #             higher_found = False
            #             idx = -1
            #             j-=1
            #         else:
            #             max_gain= prices[j]-prices[i]
            #             idx = j
            #     j += 1
            # if idx != -1:
            #     profits.append(prices[idx] - prices[i] + self.maxProfit(min(k - 1, len(prices[idx + 1:]) // 2), prices[idx + 1:]))
            max_profit = self.maxProfit(min(k, len(prices[i+1:])//2), prices[i+1:])
            max_gain = 0
            for j in range(i+1, len(prices)):
                if (prices[j] - prices[i]) > max_gain: #and (prices[j]-prices[i] + self.maxProfit(min(29,len(prices[j+1:])//2),prices[j+1:]))> max_profit:
                    max_gain = prices[j] - prices[i]
                    val = max_gain + self.maxProfit(min(k-1, len(prices[j+1:])//2), prices[j+1:])
                    if val > max_profit:
                        max_profit = val
        self.cache[key] = max_profit
        return max_profit
29316