https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv

This problem is just extension of problem 123. Best Time to Buy and Sell Stock III

Explanations are exactly the same as problem 123: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/794633/Python-O(n)-solution-with-optimization-explained

Complexity: time and space complexity is O(nk), space comlexity can be improved to O(k)

class Solution:
    def maxProfit(self, k, prices):
        if len(prices) <= 1 or k == 0: return 0
        
        delta = [prices[i+1]-prices[i] for i in range (len(prices)-1)]
        B=[sum(delta) for _, delta in groupby(delta, key=lambda x: x < 0)]
        n = len(B) + 1

        if k > len(prices)//2: return sum(x for x in B if x > 0)
        
        dp = [[0]*(k+1) for _ in range(n-1)] 
        mp = [[0]*(k+1) for _ in range(n-1)] 

        dp[0][1], mp[0][1] = B[0], B[0]

        for i in range(1, n-1):
            for j in range(1, k+1):
                dp[i][j] = max(mp[i-1][j-1], dp[i-1][j]) + B[i]
                mp[i][j] = max(dp[i][j], mp[i-1][j])

        return max(mp[-1])

If you like the solution, you can upvote it on leetcode discussion section: Problem 0188