Code Implementation

class Solution:
    def maxSumAfterPartitioning(self, arr, k):
        n = len(arr)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            cur_max = 0
            for j in range(1, min(k, i) + 1):
                cur_max = max(cur_max, arr[i - j])
                dp[i] = max(dp[i], dp[i - j] + cur_max * j)
        return dp[n]
      

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            int cur_max = 0;
            for (int j = 1; j <= min(k, i); ++j) {
                cur_max = max(cur_max, arr[i - j]);
                dp[i] = max(dp[i], dp[i - j] + cur_max * j);
            }
        }
        return dp[n];
    }
};
      

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            int curMax = 0;
            for (int j = 1; j <= Math.min(k, i); ++j) {
                curMax = Math.max(curMax, arr[i - j]);
                dp[i] = Math.max(dp[i], dp[i - j] + curMax * j);
            }
        }
        return dp[n];
    }
}
      

var maxSumAfterPartitioning = function(arr, k) {
    const n = arr.length;
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        let curMax = 0;
        for (let j = 1; j <= Math.min(k, i); ++j) {
            curMax = Math.max(curMax, arr[i - j]);
            dp[i] = Math.max(dp[i], dp[i - j] + curMax * j);
        }
    }
    return dp[n];
};
      

Problem Description

Given an integer array arr and an integer k, you are allowed to split the array into contiguous subarrays, where each subarray has at most k elements. For each subarray, every element is replaced by the maximum element in that subarray, and the sum of all the elements in the modified array is calculated.

Your task is to determine the maximum possible sum obtainable by partitioning the array this way.

• Each element must be used exactly once, and partitions must be contiguous.
• You cannot reuse elements or skip any elements.
• There is always at least one valid way to partition the array.

Example:
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

Thought Process

At first glance, this problem seems to require checking all possible ways to split the array into subarrays of length at most k. For each possible partition, we would compute the sum after replacing each subarray's elements with the subarray's maximum value. However, the number of possible partitions grows very quickly, making brute-force approaches inefficient.

To optimize, we can think recursively: for each position in the array, we can try ending the last partition at that position with length 1 up to k, and for each, compute the maximum sum possible. This naturally leads to a dynamic programming (DP) approach, where we store the best result up to each index and build up to the full array.

Solution Approach

We use a bottom-up dynamic programming strategy to solve this problem efficiently.

1. DP Array Definition: We define a DP array dp where dp[i] represents the maximum sum we can obtain by partitioning the first i elements of arr.
2. Base Case: dp[0] = 0 since an empty array has sum 0.
3. Transition: For each position i (from 1 to n), we consider all possible partition sizes j (from 1 to k), as long as i - j ≥ 0. For each, we:
   • Find the maximum element cur_max in the last j elements ending at i-1.
   • Compute the sum as dp[i-j] + cur_max * j.
   • Take the maximum over all possible j to update dp[i].
4. Result: dp[n] gives the answer for the full array.

We use a DP array because each state depends only on previous states, and lookups/updates are fast. This avoids redundant computation and ensures we only consider valid partitions.

Example Walkthrough

Let's walk through the example arr = [1,15,7,9,2,5,10], k = 3:

1. i = 1: Only one partition possible: [1]. Max = 1. dp[1] = 1
2. i = 2:
   • Partition size 1: [15], max = 15, dp[1] + 15 = 16
   • Partition size 2: [1,15], max = 15, dp[0] + 15*2 = 30
   dp[2] = 30
3. i = 3:
   • Partition size 1: [7], max = 7, dp[2] + 7 = 37
   • Partition size 2: [15,7], max = 15, dp[1] + 15*2 = 31
   • Partition size 3: [1,15,7], max = 15, dp[0] + 15*3 = 45
   dp[3] = 45
4. Continue similarly for i = 4 through i = 7, always checking the last 1, 2, or 3 elements, and updating dp[i] with the best sum.
5. Final result: dp[7] = 84

At each step, we ensure we always use the best possible partition ending at that position.

Time and Space Complexity

• Brute-force: Exponential time, since every possible way to partition the array is considered.
• Optimized DP: For each i (from 1 to n), we check up to k previous elements. So, time complexity is O(n * k).
• Space Complexity: We use a dp array of size n+1, so O(n) space.

This is efficient and works well within typical constraints.

Summary

The key insight is to use dynamic programming to efficiently compute the maximum sum after partitioning. By considering all possible partition sizes up to k for each position, and always keeping track of the best sum so far, we avoid redundant computation. The DP approach is elegant because it transforms an exponential brute-force problem into a linear one with respect to the array size, making it practical for large inputs.