Problem description

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3 Output: 84 Explanation: A becomes [15,15,15,9,10,10,10]

Note:

1 <= K <= A.length <= 500 0 <= A[i] <= 10^6

Solution

1. Let DP[i] be the partition maximum sum of array A[:i], then we can build DP[i] based on subproblems. That is:
2. If A[i - 1] is the only element in the last partition we have DP[i - 1] + 1 x A[i - 1]
3. If A[i - 1] and A[i - 2] are the only elements in the last partition we have DP[i - 2] + 2 x max(A[i - 2], A[i -1])
4. ….
5. If A[i - 1] ,,,A[i - K] are the only elements in the last partition we have DP[i - K] + K x max(A[i - K],,A[i - 1])
6. We take the maximum among all the cases

Below is my python implementation

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        '''
        DP[i] = (DP[i - 1] + A[i - 1], DP[i - 2], max(A[i - 1], A[i - 2]), .., DP[i - K] + max(A[i - 1], ..., A[i - K])
        '''
        n = len(A)
        DP = [0 for i in range(n + 1)]
        for i in range(1, K + 1):
            DP[i] = max(A[:i]) * i
        for i in range(K + 1, n + 1):
            temp = -float('inf')
            for j in range(1, K + 1):
                temp = max(temp, A[i - j])
                DP[i] = max(DP[i], DP[i - j] + j * temp)
        return DP[n]