1043. Partition Array for Maximum Sum - Explanation

1. Recursion

Intuition

We need to partition the array into subarrays of length at most k, where each element in a subarray becomes the maximum value of that subarray. The goal is to maximize the total sum after this transformation.

At each position, we have a choice: end the current subarray at any of the next k positions. For each choice, we calculate the contribution (maximum element times subarray length) and recursively solve the remaining array. We try all valid partition lengths and take the maximum result.

Algorithm

Define a recursive function starting at index i.
Base case: if i reaches the end of the array, return 0.
For each possible subarray ending at positions i to min(i + k - 1, n - 1):
- Track the maximum element seen so far in this subarray.
- Calculate the sum contribution as max element times window size.
- Recursively solve for the rest of the array starting at j + 1.
- Keep track of the best total sum.
Return the maximum sum found.

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        def dfs(i):
            if i >= len(arr):
                return 0

            cur_max = 0
            res = 0
            for j in range(i, min(len(arr), i + k)):
                cur_max = max(cur_max, arr[j])
                window_size = j - i + 1
                res = max(res, dfs(j + 1) + cur_max * window_size)

            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(k ^ n)$
Space complexity: $O(n)$ for recursion stack.

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems. When we compute the maximum sum starting from index i, we might need this value multiple times from different partition choices. By caching results, we avoid redundant calculations.

This is the memoized version of the recursive approach. We store computed results in a cache and return them directly when we encounter the same subproblem again.

Algorithm

Create a cache dictionary with base case: cache[n] = 0.
Define a recursive function with memoization starting at index i.
If i is in the cache, return the cached value immediately.
Try all possible subarray lengths from 1 to k:
- Track the maximum element in the current window.
- Calculate contribution and add the recursive result for the remaining array.
- Take the maximum across all choices.
Store the result in the cache and return it.

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        cache = { len(arr) : 0 }

        def dfs(i):
            if i in cache:
                return cache[i]

            cur_max = 0
            res = 0
            for j in range(i, min(len(arr), i + k)):
                cur_max = max(cur_max, arr[j])
                window_size = j - i + 1
                res = max(res, dfs(j + 1) + cur_max * window_size)

            cache[i] = res
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(n)$

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .

3. Dynamic Programming (Bottom-Up)

Intuition

We can flip the top-down approach to bottom-up by filling the DP table from right to left. dp[i] represents the maximum sum achievable for the subarray starting at index i.

Starting from the last element and working backwards, we build up solutions to larger subproblems using already-computed smaller ones. This eliminates recursion overhead and makes the memory access pattern more predictable.

Algorithm

Create a DP array of size n + 1 initialized to 0 (base case is dp[n] = 0).
Iterate from i = n - 1 down to 0:
- Track the maximum element for the current window starting at i.
- For each valid window ending at j (up to i + k - 1):
  - Update the maximum element.
  - Calculate the sum as max element times window size plus dp[j + 1].
  - Update dp[i] with the maximum value found.
Return dp[0] as the answer.

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

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

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(n)$

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .

4. Dynamic Programming (Space Optimized)

Intuition

Looking at the bottom-up solution, we notice that dp[i] only depends on dp[i+1] through dp[i+k]. We never need values more than k positions ahead. This means we can reduce our space from O(n) to O(k) using a circular buffer.

We use modulo arithmetic to wrap around and reuse array positions. This technique is common when the recurrence relation has a bounded look-ahead.

Algorithm

Create a DP array of size k (using circular indexing).
Initialize dp[0] = arr[0] as the base case.
Iterate from i = 1 to n - 1:
- For each position, look backwards at windows of size 1 to k.
- Track the maximum element in each window.
- Compute the sum using circular array indexing: dp[(j-1) % k] for the previous subproblem.
- Store the best result at dp[i % k].
Return dp[(n-1) % k] as the answer.

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * k
        dp[0] = arr[0]

        for i in range(1, len(arr)):
            cur_max = 0
            max_at_i = 0
            for j in range(i, i - k, -1):
                if j < 0:
                    break
                cur_max = max(cur_max, arr[j])
                window_size = i - j + 1
                cur_sum = cur_max * window_size
                sub_sum = dp[(j - 1) % k] if j > 0 else 0
                max_at_i = max(max_at_i, cur_sum + sub_sum)

            dp[i % k] = max_at_i

        return dp[(len(arr) - 1) % k]

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(k)$

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .

Common Pitfalls

Misunderstanding the Transformation

Each element in a partition becomes the maximum value of that partition, not stays as its original value. The sum contribution is max_element * partition_length, not the sum of original elements. This transformation is the key insight of the problem.

Incorrect Window Size Calculation

When iterating through possible partition endpoints, the window size is j - i + 1, not j - i. Off-by-one errors here lead to underestimating the contribution of each partition and returning a smaller sum than optimal.

Forgetting to Track Running Maximum

For each partition starting at index i, you must track the maximum element seen so far as you extend the window. Recalculating the maximum from scratch for each window length turns an O(nk) solution into O(nk^2).