Problem statement

https://binarysearch.com/problems/K-Maximum-Non-Overlapping-Sums/

Solution

Similar to Leetcode 0123. Best Time to Buy and Sell Stock III, but be careful with edge cases. We need to put -inf in the beginning to all elements except the first row.

Complexity

Code

class Solution:
    def solve(self, B, k):
        n = len(B)
        
        dp = [[-float("inf")]*(k+1) for _ in range(n)] 
        mp = [[-float("inf")]*(k+1) for _ in range(n)]
        for i in range(n): mp[i][0] = 0

        for i in range(n):
            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 mp[-1][-1]