Problem
Given an integer array arr
, 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. Test cases are generated so that the answer fits in a *32-bit* integer.**
Example 1:
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
Example 2:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
Example 3:
Input: arr = [1], k = 1
Output: 1
Constraints:
1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length
Solution
/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
var maxSumAfterPartitioning = function(arr, k) {
var dp = Array(arr.length).fill(0);
for (var i = 0; i < arr.length; i++) {
var maxValue = 0;
for (var j = 1; j <= k && j - 1 <= i; j++) {
maxValue = Math.max(maxValue, arr[i - j + 1]);
dp[i] = Math.max(dp[i], ( dp[i - j + 1] + maxValue * j);
}
}
return dp[arr.length];
};
Explain:
dp[i + 1]
represents array [0 ... i]
's maxSumAfterPartitioning. (dp[0] = 0 means nothing, it just helps calculate.)
dp[i] = max(
dp[i - 1] + max(arr[i]) * 1,
dp[i - 2] + max(arr[i], arr[i - 1]) * 2,
...
dp[i - k] + max(arr[i], arr[i - 1], ..., arr[i - k]) * k
)
dp[arr.length - 1]
would be the answer in the end of the iteration.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).