[LeetCode] Medium - 1043. Partition Array for Maximum Sum

Source From Here
Question
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

Naive Approach (DP)

view plaincopy to clipboardprint?

1. class Solution:  
2.     def maxSumAfterPartitioning(self, A, K):  
3.         # 0) Initialization  
4.         #    best_a is used to keep past computation result  
5.         #    best_a[i] is to keep local optimal result of A[0:i-1]  
6.         best_a = [0] * len(A)  
7.         best_a[0] = A[0]  
8.   
9.         # 1) Iteratively fill the best_a with local optimal result  
10.         #    best_a[0] = A[0]  
11.         #    best_a[1] = max(best_a[0] + A[1], max(A[0:2]) * 2)  
12.         #    best_a[2] = max(best_a[1] + A[2], best_a[0] + max(A[1:3]) * 2, max(A[0:3]) * 3)  
13.         #    ...  
14.         #    best_a[n] = max(best_a[n-1] + A[n], best_a[n-2] + max(A[n-1:n+1]) * 2, ..., max(A[n-K+1:n+1]) * K)  
15.         for i in range(1, len(A)):  
16.             max_v = 0  
17.             for j in range(i, max(-1, i-K), -1):  
18.                 sa = A[j:i+1]  
19.                 v = best_a[j-1] + max(sa) * len(sa)  
20.                 if v > max_v:  
21.                     max_v = v  
22.   
23.             best_a[i] = max_v  
24.   
25.         # 2) The global optimal result is kept in last element  
26.         return best_a[-1]  

Supplement
* 花花酱 LeetCode 1043. Partition Array for Maximum Sum - 刷题找工作 EP250