Partition Array for Maximum Sum: DP with Partition Choices

You are given an integer array arr and an integer k. You can partition the array into contiguous subarrays where each subarray has at most k elements. After partitioning, every element in a subarray becomes equal to the maximum value of that subarray. Return the largest possible sum of the modified array.

This is LeetCode 1043: Partition Array for Maximum Sum, and it is one of the cleanest examples of the partition DP pattern. Unlike problems where you split an array and minimize a cost, here you are maximizing value by choosing how to group elements together.

Why this problem matters

Partition DP shows up in many forms across LeetCode. Problems like Palindrome Partitioning II, Split Array Largest Sum, and this one all share the same core structure: at each position, you try all valid partition lengths ending at that position, and pick the best one.

What makes this problem a great starting point is that the recurrence is clean and the partition constraint (at most k elements) is easy to work with. Once you understand how to try all partition sizes at each index, the same idea transfers directly to harder partition problems.

The key insight

Define dp[i] as the maximum sum achievable for the first i elements of the array. For each position i, consider every possible last partition of length j (from 1 to k). The last j elements all become the maximum value in that window, contributing max_value * j to the sum. The rest of the array is handled optimally by dp[i - j].

The recurrence is:

dp[i] = max(dp[i - j] + max(arr[i-j..i-1]) * j) for j from 1 to min(k, i)

As you extend the partition backward (increasing j), you track the running maximum. This avoids rescanning the window each time and keeps the inner loop efficient.

The solution

def maxSumAfterPartitioning(arr, k):
    n = len(arr)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        cur_max = 0
        for j in range(1, min(k, i) + 1):
            cur_max = max(cur_max, arr[i - j])
            dp[i] = max(dp[i], dp[i - j] + cur_max * j)
    return dp[n]

The outer loop processes each position from 1 to n. The inner loop tries every partition length from 1 to k, maintaining a running cur_max as it extends the partition backward. At each step, dp[i - j] + cur_max * j represents the total sum if the last partition covers the previous j elements.

Notice how cur_max updates incrementally. When j=1, it is just arr[i-1]. When j=2, it becomes max(arr[i-1], arr[i-2]). This rolling maximum means you never need a separate scan of the partition window.

Visual walkthrough

Notice how the DP table builds left to right, and at each position the algorithm looks back at most k steps. The final answer dp[7]=84 corresponds to the partition [1,15,7] | [9] | [2,5,10], where each subarray is replaced by its maximum: [15,15,15,9,10,10,10].

Complexity analysis

The outer loop runs n times and the inner loop runs at most k times per iteration, giving O(n * k) total work. The DP array uses O(n) space. Since k is bounded by n, the worst case is O(n^2), but in practice k is typically much smaller.

The building blocks

1. Partition DP recurrence

The core pattern: at each index i, try all valid partition sizes ending at i. For each choice, combine the cost of the current partition with the optimal solution for everything before it. This is the same structure used in Palindrome Partitioning II (try all palindromic endings) and Word Break (try all dictionary word endings).

The general template looks like this:

for i in range(1, n + 1):
    for j in range(1, min(k, i) + 1):
        dp[i] = best(dp[i], dp[i - j] + cost_of_partition(i - j, i))

2. Tracking running max in a window

Instead of computing the maximum of each candidate partition from scratch, extend the partition one element at a time and update a running max. This turns what could be an O(k) scan per partition length into O(1) per extension, keeping the overall inner loop at O(k) instead of O(k^2).

This incremental approach works because each partition size j+1 includes all elements of partition size j plus one more. The maximum can only stay the same or increase.

Edge cases

• k = 1: No partitioning benefit. Every element stays as itself, and the answer is just the sum of the array.
• k >= n: The entire array can be one partition. Every element becomes the global maximum, so the answer is max(arr) * n.
• All elements equal: Any partition gives the same result. The answer is arr[0] * n.
• Array of length 1: Only one element, one partition. Return arr[0].
• Descending array: Grouping smaller elements with larger ones to the left is beneficial. The DP naturally discovers this.

From understanding to recall

You can probably trace through the DP table now and see why each value is what it is. But will you be able to set up the recurrence from scratch next week? The partition DP pattern is deceptively simple to follow along with, and easy to forget when you need to write it yourself.

Spaced repetition bridges that gap. You revisit the partition DP template at increasing intervals, reconstruct the inner loop logic from memory, and after a few reps the pattern becomes automatic. This one template covers a whole family of partition problems, so drilling it once pays off across many future encounters.

Related posts

• Split Array Largest Sum - Another partition DP problem with binary search
• Palindrome Partitioning II - Partition DP for minimum cuts
• Coin Change - Classic DP with choices at each step

CodeBricks organizes problems like Partition Array for Maximum Sum by their underlying building blocks, not by surface-level tags. When you drill the partition DP pattern, you are also preparing for Split Array Largest Sum, Word Break, and every other problem that uses the same recurrence shape. That kind of transfer is what turns practice into real interview readiness.