LeetCode 1043 - Partition Array for Maximum Sum

The problem gives us an integer array arr and an integer k. We are allowed to partition the array into contiguous subarrays where each subarray has length at most k.

leetcodemediumarraydynamic-programming

LeetCode Problem 1043

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us an integer array arr and an integer k. We are allowed to partition the array into contiguous subarrays where each subarray has length at most k.

After choosing the partitions, every element inside a partition is replaced with the maximum value from that partition. The final score is the sum of the transformed array, and our goal is to maximize this total sum.

For example, suppose we choose a partition [1, 15, 7]. The maximum value inside this partition is 15, so the partition becomes [15, 15, 15]. Its contribution to the final answer becomes:

15 * 3 = 45

The challenge is deciding where to place the partition boundaries so that the total transformed sum becomes as large as possible.

The input consists of:

  • arr, the original integer array
  • k, the maximum allowed partition size

The output is a single integer representing the maximum achievable sum after performing the optimal partitioning.

The constraints are important:

  • arr.length <= 500
  • k <= arr.length

An array length of 500 is small enough for quadratic dynamic programming solutions, but far too large for exhaustive recursion that tries every possible partitioning arrangement.

Another important detail is that array values can be as large as 10^9, so intermediate sums can become large. However, the problem guarantees that the final answer fits inside a 32 bit integer.

Several edge cases are worth identifying early:

  • Arrays of length 1
  • k = 1, meaning no meaningful grouping is possible
  • k = n, meaning the entire array may become one partition
  • Strictly increasing arrays where larger later values encourage larger partitions
  • Strictly decreasing arrays where smaller partition sizes may be better
  • Arrays containing zeros

A naive implementation can easily recompute overlapping subproblems many times, which leads to exponential complexity.

Approaches

Brute Force Approach

The brute force solution tries every possible partitioning configuration.

At each position, we can create a partition of length:

1, 2, 3, ..., k

as long as the partition remains inside array bounds.

For each chosen partition:

  1. Find the maximum value inside that partition
  2. Compute the contribution:
partition_length * partition_max
  1. Recursively solve the remaining suffix of the array

This guarantees correctness because it explores every valid partition arrangement.

However, the same suffix subarrays are recomputed repeatedly. For example, the optimal answer for index 5 may be calculated from many different recursive paths.

The number of partition combinations grows exponentially, making this approach too slow.

Key Insight for the Optimal Solution

The critical observation is that the problem has overlapping subproblems.

Define:

dp[i] = maximum sum obtainable for the first i elements

To compute dp[i], we consider every possible partition ending at index i - 1.

Suppose the final partition has length len.

Then:

  • The partition starts at:
i - len
  • We track the maximum value inside that partition
  • Its contribution becomes:
partition_max * len
  • Everything before the partition is already optimally solved by:
dp[i - len]

So:

dp[i] = max(
    dp[i - len] + partition_max * len
)

for all valid partition lengths.

This transforms the exponential recursion into a polynomial time dynamic programming solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k^n) O(n) Tries every partition combination recursively
Optimal Dynamic Programming O(n * k) O(n) Builds optimal answers incrementally using DP

Algorithm Walkthrough

  1. Create a DP array dp of size n + 1.

dp[i] will represent the maximum achievable sum using the first i elements of the array.

Initialize:

dp[0] = 0

because an empty array contributes zero sum. 2. Iterate through the array from left to right.

For each position i, we want to compute the best answer for the first i elements. 3. Consider every possible partition ending at position i - 1.

The partition can have lengths:

1 to k

as long as the starting index remains valid. 4. While expanding the partition backward, maintain the maximum element seen so far.

This is important because recomputing the maximum repeatedly would increase complexity unnecessarily.

For example:

partition = arr[j:i]

Keep updating:

current_max = max(current_max, arr[j])
  1. Compute the contribution of the current partition.

If the partition length is:

length = i - j

then its transformed contribution becomes:

current_max * length
  1. Combine the partition contribution with the best solution before the partition.

The total candidate value becomes:

dp[j] + current_max * length
  1. Take the maximum over all valid partition lengths.

This ensures we choose the optimal final partition for position i. 8. After filling the DP table, return:

dp[n]

which represents the optimal answer for the entire array.

Why it works

The dynamic programming recurrence works because every valid solution can be viewed as:

(best solution before final partition) +
(contribution of final partition)

The partitions are independent once the boundary is fixed. Since dp[j] already stores the optimal solution for the prefix ending before the final partition, combining it with every possible final partition guarantees that we examine all valid optimal constructions.

Because we take the maximum over all partition lengths, the final answer must be optimal.

Python Solution

from typing import List

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):
            current_max = 0

            for j in range(i - 1, max(-1, i - k - 1), -1):
                current_max = max(current_max, arr[j])

                partition_length = i - j

                dp[i] = max(
                    dp[i],
                    dp[j] + current_max * partition_length
                )

        return dp[n]

The implementation begins by creating a DP array where dp[i] stores the best possible answer using the first i elements.

The outer loop iterates over every possible prefix length. For each i, we compute the optimal value for that prefix.

The inner loop walks backward from index i - 1 to at most k elements behind. This backward traversal represents trying every possible final partition ending at i - 1.

current_max is updated incrementally while expanding the partition backward. This avoids rescanning the partition repeatedly.

For every candidate partition:

arr[j:i]

we calculate:

dp[j] + current_max * partition_length

This represents:

  • the optimal solution before the partition
  • plus the transformed value contributed by the current partition

Finally, dp[n] contains the optimal answer for the entire array.

Go Solution

func maxSumAfterPartitioning(arr []int, k int) int {
	n := len(arr)

	dp := make([]int, n+1)

	for i := 1; i <= n; i++ {
		currentMax := 0

		start := i - k
		if start < 0 {
			start = 0
		}

		for j := i - 1; j >= start; j-- {
			if arr[j] > currentMax {
				currentMax = arr[j]
			}

			partitionLength := i - j

			candidate := dp[j] + currentMax*partitionLength

			if candidate > dp[i] {
				dp[i] = candidate
			}
		}
	}

	return dp[n]
}

The Go implementation follows the exact same dynamic programming logic as the Python solution.

One difference is that Go does not provide a built in max() function for integers, so comparisons are performed manually using if statements.

Slices are used for the DP array, and all integers fit safely within Go's int type under the problem constraints.

Worked Examples

Example 1

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

We build the DP table progressively.

Initial state:

dp = [0,0,0,0,0,0,0,0]

i = 1

Possible partition:

Partition Max Length Candidate
[1] 1 1 0 + 1 = 1 
dp[1] = 1

i = 2

Possible partitions:

Partition Max Length Candidate
[15] 15 1 dp[1] + 15 = 16
[1,15] 15 2 dp[0] + 30 = 30 
dp[2] = 30

i = 3

Possible partitions:

Partition Max Length Candidate
[7] 7 1 37
[15,7] 15 2 31
[1,15,7] 15 3 45 
dp[3] = 45

i = 4

Possible partitions:

Partition Max Length Candidate
[9] 9 1 54
[7,9] 9 2 48
[15,7,9] 15 3 46 
dp[4] = 54

i = 5

Possible partitions:

Partition Max Length Candidate
[2] 2 1 56
[9,2] 9 2 63
[7,9,2] 9 3 57 
dp[5] = 63

i = 6

Possible partitions:

Partition Max Length Candidate
[5] 5 1 68
[2,5] 5 2 64
[9,2,5] 9 3 72 
dp[6] = 72

i = 7

Possible partitions:

Partition Max Length Candidate
[10] 10 1 82
[5,10] 10 2 83
[2,5,10] 10 3 84 
dp[7] = 84

Final answer:

84

Example 2

arr = [1,4,1,5,7,3,6,1,9,9,3]
k = 4

The algorithm continuously evaluates all partition sizes from 1 to 4 at every position and stores the optimal prefix sums.

Final result:

83

Example 3

arr = [1]
k = 1

Only one partition is possible:

Partition Contribution
[1] 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n * k) For each index, we try at most k partition lengths
Space O(n) DP array stores one value per prefix

The outer loop runs n times, and for each position we scan backward at most k elements. Therefore the total work is:

O(n * k)

The algorithm only stores the DP array and a few variables, so the extra memory usage is linear.

Test Cases

from typing import List

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):
            current_max = 0

            for j in range(i - 1, max(-1, i - k - 1), -1):
                current_max = max(current_max, arr[j])

                partition_length = i - j

                dp[i] = max(
                    dp[i],
                    dp[j] + current_max * partition_length
                )

        return dp[n]

sol = Solution()

assert sol.maxSumAfterPartitioning(
    [1, 15, 7, 9, 2, 5, 10], 3
) == 84  # provided example 1

assert sol.maxSumAfterPartitioning(
    [1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3], 4
) == 83  # provided example 2

assert sol.maxSumAfterPartitioning(
    [1], 1
) == 1  # single element array

assert sol.maxSumAfterPartitioning(
    [5, 5, 5, 5], 2
) == 20  # all equal values

assert sol.maxSumAfterPartitioning(
    [1, 2, 3, 4, 5], 5
) == 25  # entire array can become all 5s

assert sol.maxSumAfterPartitioning(
    [5, 4, 3, 2, 1], 1
) == 15  # no grouping allowed

assert sol.maxSumAfterPartitioning(
    [10, 1, 1, 1], 4
) == 40  # large value dominates full partition

assert sol.maxSumAfterPartitioning(
    [0, 0, 0], 2
) == 0  # all zeros

assert sol.maxSumAfterPartitioning(
    [2, 9, 1], 2
) == 20  # optimal split uses size 2 partition

assert sol.maxSumAfterPartitioning(
    [7, 6, 5, 4, 3], 3
) == 33  # decreasing sequence
Test Why
[1,15,7,9,2,5,10], k=3 Validates main example behavior
[1,4,1,5,7,3,6,1,9,9,3], k=4 Tests larger mixed array
[1], k=1 Smallest possible input
[5,5,5,5], k=2 Ensures equal values work correctly
[1,2,3,4,5], k=5 Entire array can become one partition
[5,4,3,2,1], k=1 No partition expansion allowed
[10,1,1,1], k=4 Large maximum dominates partition
[0,0,0], k=2 Handles zero values correctly
[2,9,1], k=2 Tests nontrivial partition choice
[7,6,5,4,3], k=3 Decreasing values stress partition decisions

Edge Cases

One important edge case occurs when k = 1. In this situation, every partition must contain exactly one element. No transformation actually changes the array because each partition maximum equals the element itself. A buggy implementation might still attempt larger partitions or incorrectly update DP transitions. The current implementation handles this naturally because the inner loop only considers partitions of size 1.

Another critical edge case is when k = n. In this case, the entire array may become a single partition. The algorithm correctly evaluates all partition lengths up to the full array size, allowing it to discover whether transforming the entire array into the global maximum produces the best result.

Arrays containing repeated or identical values can also expose logical bugs. If maximum tracking is implemented incorrectly, the algorithm may fail to preserve the correct partition maximum while expanding backward. The implementation avoids this issue by incrementally updating current_max during the backward traversal.

A final subtle edge case involves arrays containing zeros. Since partition contributions can become zero, implementations that incorrectly initialize DP values or maximum values may produce invalid results. The algorithm safely initializes current_max to zero and always computes candidates using valid partition ranges.