Partition Array for Maximum Sum — Problem & Solution
Partition Array for Maximum Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Partition Array for Maximum Sum is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and HCL interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Adobe, HCL
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Partition arr into contiguous subarrays of length at most k. After partitioning, every value in a subarray becomes that subarray's maximum.
Return the largest possible sum of the resulting array.
Example 1
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: `[15,15,15,9,10,10,10]` sums to 84.
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 <= 5000 <= arr[i] <= 10^91 <= k <= arr.length
Hints for Partition Array for Maximum Sum
Hint 1
dp[i]= the best sum for the firstielements.Hint 2
The last subarray ends at
i-1and has some length from 1 tok.Hint 3
Extend that last subarray leftwards, keeping its running maximum as you go.
How to solve Partition Array for Maximum Sum
Prefix DP. dp[i] is the best total for arr[0..i-1]. The final subarray has length len between 1 and k; extending it leftwards lets you keep its maximum in a running variable, so each candidate is dp[i-len] + max · len.
Approach
- Set
dp[0] = 0. - For each
ifrom 1 ton, walklenfrom 1 tomin(k, i), updatingpeak = max(peak, arr[i-len]). - Take the best
dp[i-len] + peak · len.
Why it works
Growing the last block leftwards is what makes the inner loop O(1) per step: the maximum of a window that only ever extends is a single running comparison, so no separate max query is needed. Trying to be greedy — always cutting at the largest value — fails, because a small value is often worth absorbing into a block so that a nearby large value is multiplied more times.
Complexity
- Time —
O(n · k) - Space —
O(n)
Pitfalls
- Subarrays have length at most
k, not exactlyk. - The running maximum must reset for each
i; carrying it across resets inflates earlier blocks. - Values reach 10⁹ and blocks reach length
k, so the running sum needs 64 bits at the upper bound.
Reference solution
Python
from typing import List
def maxSumAfterPartitioning(arr: List[int], k: int) -> int:
n = len(arr)
dp = [0] * (n + 1)
for i in range(1, n + 1):
peak = 0
best = 0
for length in range(1, min(k, i) + 1):
peak = max(peak, arr[i - length])
best = max(best, dp[i - length] + peak * length)
dp[i] = best
return dp[n]Java
public static int maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length;
long[] dp = new long[n + 1];
for (int i = 1; i <= n; i++) {
long best = 0;
long peak = 0;
for (int len = 1; len <= k && len <= i; len++) {
peak = Math.max(peak, arr[i - len]);
best = Math.max(best, dp[i - len] + peak * len);
}
dp[i] = best;
}
return (int) dp[n];
}C++
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = (int) arr.size();
vector<long long> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long best = 0, peak = 0;
for (int len = 1; len <= k && len <= i; len++) {
peak = max(peak, (long long) arr[i - len]);
best = max(best, dp[i - len] + peak * len);
}
dp[i] = best;
}
return (int) dp[n];
}JavaScript
var maxSumAfterPartitioning = function(arr, k) {
var n = arr.length, i;
var dp = [];
for (i = 0; i <= n; i++) dp.push(0);
for (i = 1; i <= n; i++) {
var best = 0, peak = 0;
for (var len = 1; len <= k && len <= i; len++) {
if (arr[i - len] > peak) peak = arr[i - len];
var cand = dp[i - len] + peak * len;
if (cand > best) best = cand;
}
dp[i] = best;
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming