Partition Array for Maximum Sum — Medium Problem & Solution

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 <= 500
• 0 <= arr[i] <= 10^9
• 1 <= k <= arr.length

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

1. Set dp[0] = 0.
2. For each i from 1 to n, walk len from 1 to min(k, i), updating peak = max(peak, arr[i-len]).
3. 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 exactly k.
• 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium