Partition Array for Maximum Sum — Solution

Problem

You have an integer array and can partition it into any number of contiguous subarrays, as long as no subarray has more than k elements. After partitioning, every element in a subarray becomes the maximum value of that subarray. Find the largest possible total sum after this transformation.

• Input: arr = [1, 15, 7, 9, 2, 5, 10], k = 3
• Output: 84
• Explanation: Partitioning as [1,15,7] | [9] | [2,5,10] gives [15,15,15] | [9] | [10,10,10] = 45 + 9 + 30 = 84.

Intuition

The decision at each position is: how long should the last subarray be? If we know the best total for every prefix, we can extend it by choosing a last window of length 1 to k, substituting the window's maximum for every element in that window. This optimal substructure — best answer for a prefix depends only on shorter prefixes — makes it a clean 1D DP.

Solution — Bottom-Up DP

Build dp[i] = maximum achievable sum for the first i elements. For each position, try every window size j from 1 to min(k, i), track the running window max as j grows, and update dp[i] with dp[i-j] + window_max * j.

1. Initialize dp of length n + 1 with all zeros (dp[0] = 0 is the empty-prefix base case).
2. For each index i from 1 to n: a. Iterate j from 1 to min(k, i) — these are the possible last-window sizes. b. Maintain window_max as the maximum of arr[i-j .. i-1], updating it as j increases. c. Set dp[i] = max(dp[i], dp[i-j] + window_max * j).
3. Return dp[n].

1def maxSumAfterPartitioning(arr: list[int], k: int) -> int:
2    n = len(arr)
3    dp = [0] * (n + 1)  # dp[i] = best sum for first i elements
4
5    for i in range(1, n + 1):
6        window_max = 0
7        # try every window length from 1 up to min(k, i)
8        for j in range(1, min(k, i) + 1):
9            window_max = max(window_max, arr[i - j])  # extend window leftward
10            dp[i] = max(dp[i], dp[i - j] + window_max * j)
11
12    return dp[n]

Time: O(n × k) — for each of the n positions we scan back at most k steps.

Space: O(n) — the dp array of length n + 1.

Complexity Summary

Common Mistakes

• Using the global array max instead of the local window max — only elements inside the current window can be inflated; extending window_max leftward one step at a time keeps it local.
• Letting j exceed i — the window can't be longer than the prefix itself; the bound min(k, i) is essential when i < k.
• Sizing dp as n instead of n + 1 — dp[i] represents a prefix of length i, so you need indices 0 through n inclusive.
• Recomputing the window max with a slice — calling max(arr[i-j:i]) inside the loop is O(k) per step and redundant; the incremental window_max = max(window_max, arr[i-j]) achieves the same in O(1).
• Trying a greedy approach — always picking the largest element visible doesn't work; which window to group it with depends on what's to its left, which is exactly what DP captures.

Related Problems

• maximum-subarray — foundational 1D DP where each position extends or restarts a subarray
• house-robber — 1D DP with a local constraint on which elements you can pick together
• word-break — DP over prefixes where each step tries every valid last segment
• burst-balloons — interval DP where the local choice (which balloon to pop last) determines a range's contribution
• coin-change — DP where you try every denomination as the last coin, mirroring the "try every last-window size" pattern here