BinarySearch 0865 Max Sum Partitioning

Problem statement

https://binarysearch.com/problems/Max-Sum-Partitioning/

Solution

Equal to Leetcode 1043. Partition Array for Maximum Sum.

Complexity

It is O(nk) for time and O(n) for space.

Code

class Solution:
    def solve(self, A, K):
        n = len(A)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            curMax = 0
            for k in range(min(K, i)):
                curMax = max(curMax, A[i - k - 1])
                dp[i] = max(dp[i], dp[i - k - 1] + curMax * (k + 1))
        return dp[-1]