Problem statement

https://leetcode.com/problems/partition-array-for-maximum-sum/

Solution

Notice that here k is the maximum size of subarray, not number of subarrays! Let dp[i] be the answer for A[:i+1]. Then we need to look at previous k values and keep running maximum.

Complexity

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

Code

class Solution:
     def maxSumAfterPartitioning(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]