Problem statement

https://binarysearch.com/problems/Buy-and-Sell-K-Stocks/

Solution

Equal to leetcode 0188. Best Time to Buy and Sell Stock IV

Complexity

It is O(nk) for time and space.

Code

class Solution:
    def solve(self, prices, k):  
        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])