Partition Array for Maximum Sum
Problem
Given an integer array arr, partition it into (contiguous) subarrays of length at most k. After partitioning, each subarray has all its values changed to become the maximum value of that subarray. Return the largest sum of the given array after partitioning.
arr = [1, 4, 1, 5, 3], k = 323def max_sum_after_partitioning(arr, k):
n = len(arr)
dp = [0] * (n + 1)
for i in range(1, n + 1):
best = 0
cur_max = 0
for j in range(1, min(k, i) + 1):
cur_max = max(cur_max, arr[i - j])
best = max(best, dp[i - j] + cur_max * j)
dp[i] = best
return dp[n]function maxSumAfterPartitioning(arr, k) {
const n = arr.length;
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
let best = 0, curMax = 0;
for (let j = 1; j <= Math.min(k, i); j++) {
curMax = Math.max(curMax, arr[i - j]);
best = Math.max(best, dp[i - j] + curMax * j);
}
dp[i] = best;
}
return dp[n];
}class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int best = 0, curMax = 0;
for (int j = 1; j <= Math.min(k, i); j++) {
curMax = Math.max(curMax, arr[i - j]);
best = Math.max(best, dp[i - j] + curMax * j);
}
dp[i] = best;
}
return dp[n];
}
}int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
int best = 0, curMax = 0;
for (int j = 1; j <= min(k, i); j++) {
curMax = max(curMax, arr[i - j]);
best = max(best, dp[i - j] + curMax * j);
}
dp[i] = best;
}
return dp[n];
}Explanation
The trick is to think about the answer one prefix at a time. We define dp[i] as the best total sum we can get using just the first i elements of the array, and we build it up from left to right.
To compute dp[i], we ask: how long is the last block? It can be any length j from 1 up to k. That last block covers arr[i-j..i-1], and every value in it becomes the block's maximum, so it contributes curMax * j.
Whatever came before that block is already solved in dp[i-j]. So each candidate is dp[i - j] + curMax * j, and we keep the largest over all allowed block lengths. As j grows we update curMax on the fly, so finding the block max is cheap.
Example: arr = [1, 4, 1, 5, 3], k = 3. The best split is [1, 4] then [1, 5, 3], which become [4, 4] and [5, 5, 5]. That sums to 8 + 15 = 23, which is dp[5].
The answer is dp[n]. Because each of the n positions tries at most k block lengths, the work is O(n·k).