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.
Test Cases
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 2:
Input: arr = [1], k = 1
Output: 1
How to Solve
At every index, we need to decide whether to move the element at the index to a new partition or use the existing partition
For the first test case, arr = [1,15,7,9,2,5,10], k = 3
graph TD
0 --> 1
0 --> 2
0 --> 3
1 --> 2
1 --> 3
1 --> 4
2 --> 3
2 --> 4
2 --> 5
From above graph, we can see that we are reusing some of the pre-calculated values. We should proceed with dynamic programming for this
At every index, check for all elements upto index + k and find max sum that can be made by multipying the max element in sub-array
Solution
class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
int[] dp = new int[arr.length];
Arrays.fill(dp, -1);
return maxSum(arr, k, dp, arr.length, 0);
}
private int maxSum(int[] arr, int k, int[] dp, int n, int start) {
if (start >= n) {
return 0;
}
if (dp[start] != -1) {
return dp[start];
}
int max = 0, ans = 0;
int end = Math.min(n, start + k);
for(int i = start; i < end; i++) {
max = Math.max(max, arr[i]);
ans = Math.max(ans, max*(i-start+1) + maxSum(arr, k, dp, n, i+1));
}
return dp[start] = ans;
}
}