LeetCode 1043: Partition Array for Maximum Sum

Problem Restatement

We are given an integer array arr and an integer k.

We can partition arr into contiguous subarrays of length at most k.

After partitioning, each element in a subarray is replaced by the maximum value of that subarray.

We need to return the maximum sum of the resulting array.

The official constraints state that 1 <= k <= arr.length <= 500 and 0 <= arr[i] <= 10^9.

Input and Output

Function shape:

def maxSumAfterPartitioning(arr: list[int], k: int) -> int:
    ...

Examples

Example 1:

arr = [1, 15, 7, 9, 2, 5, 10]
k = 3

Partition: [1, 15, 7], [9, 2, 5], [10].

After: [15, 15, 15, 9, 9, 9, 10]. Sum = 82.

Answer:

84

One strong partition is [1,15,7], [9], [2,5,10]. Its value is 15*3 + 9*1 + 10*3 = 84.

[1,15], [7,9,2], [5,10] → 15*2 + 9*3 + 10*2 = 30 + 27 + 20 = 77. Worse.

[1,15,7], [9], [2,5,10] → 45 + 9 + 30 = 84.

Answer: 84.

Key Insight

Let dp[i] = maximum sum for the prefix arr[:i].

For each position i, try all partition lengths l from 1 to k:

dp[i] = max(dp[i - l] + max(arr[i-l:i]) * l)

Correctness

For each ending position i and partition length l, the last partition covers arr[i-l:i]. All elements in this partition become the maximum of that partition. Adding dp[i-l] gives the best result for the prefix before the partition.

The maximum over all valid l gives the best result ending at i.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def maxSumAfterPartitioning(self, arr: list[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            cur_max = 0
            for l in range(1, min(k, i) + 1):
                cur_max = max(cur_max, arr[i - l])
                dp[i] = max(dp[i], dp[i - l] + cur_max * l)

        return dp[n]

Testing

def run_tests():
    s = Solution()

    assert s.maxSumAfterPartitioning([1,15,7,9,2,5,10], 3) == 84
    assert s.maxSumAfterPartitioning([1,4,1,5,7,3,6,1,9,9,3], 4) == 83
    assert s.maxSumAfterPartitioning([1], 1) == 1

    print("all tests passed")

run_tests()