<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>

"""
[3,2,6,5,10,3]

going down I think always makes sense for a buy
if it's less than you can just make up that profit and it'll be greater than what you otherwise would have had


-in order to make money you must sell
- looking for the biggest differences that exist
- for every number, you do or don't buy it / sell if it's lower than your buy until you hit k

[3, 6], [0, 3]
[3, 5], [0 ,3]
[2, 6], [0, 3]
how could we more efficiently know that 2-6 was going to be better than 3-6
- when you are on a sell operation, you can iterate until you find the max
- when you are on buy operation, you can iterate until you find the min


3, 2, 1, 3, 5, 4
"""
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        prices2 = []
        l, r = 0, 1

        while l < len(prices) and r < len(prices):
            while (l < len(prices) - 1) and prices[l] > prices[l + 1]:
                l += 1
            r = l + 1
            prices2.append(prices[l])
            while (r < len(prices) - 1) and prices[r] < prices[r + 1]:
                r += 1
            if r < len(prices):
                prices2.append(prices[r])
            l = r + 1

        cache = {}
        def search(idx, buying, t):
            if idx == len(prices2) or t == k:
                return 0
            
            if (idx, buying, t) in cache:
                return cache[(idx, buying, t)]
            
            if buying:
                result = max(
                    search(idx + 1, not buying, t) - prices2[idx],
                    search(idx + 1, buying, t),
                )
            else:
                result = max(
                    search(idx + 1, not buying, t + 1) + prices2[idx],
                    search(idx + 1, buying, t),
                )
            
            cache[(idx, buying, t)] = result
            return result
        
        return search(0, True, 0)

        


        
66551