Partition Array for Maximum Sum

How it works

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.

Steps

1. Create a DP array of size k (using circular indexing).
2. Initialize dp[0] = arr[0] as the base case.
3. 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].
4. Return dp[(n-1) % k] as the answer.

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.

Things to watch for

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).

from typing import List

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]

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(k);
        dp[0] = arr[0];

        for (int i = 1; i < n; i++) {
            int cur_max = 0, max_at_i = 0;
            for (int j = i; j > i - k; j--) {
                if (j < 0) break;
                cur_max = max(cur_max, arr[j]);
                int window_size = i - j + 1;
                int cur_sum = cur_max * window_size;
                int sub_sum = (j > 0) ? dp[(j - 1) % k] : 0;
                max_at_i = max(max_at_i, cur_sum + sub_sum);
            }
            dp[i % k] = max_at_i;
        }

        return dp[(n - 1) % k];
    }
};