medium Partition Array for Maximum Sum

Problem Statement

You are given an integer array arr, partition the array into subarrays of length at most k. After partitioning, change each element of a particular subarray to the maximum value of that subarray.

Return the largest possible sum of the array after partitioning.

Examples

Example 1:

• Input: arr = [1, 3, 7, 9, 2], k = 2
• Output: 33
• Explanation:
  • Partition into [1], [3, 7], [9, 2].
  • Change subarrays to their max values: [1], [7, 7], [9, 9].
  • Sum is 1 + 7 + 7 + 9 + 9 = 33.

Example 2:

• Input: arr = [4, 8, 1, 6, 5], k = 3
• Output: 36
• Explanation:
  • Partition into [4, 8, 1], [6, 5].
  • Change subarrays to their max values: [8, 8, 8], [6, 6].
  • Sum is 8 + 8 + 8 + 6 + 6 = 36.

Example 3:

• Input: arr = [2, 5, 10, 1], k = 2
• Output: 30
• Explanation:
  • Partition into [2, 5], [10, 1].
  • Change subarrays to their max values: [5, 5], [10, 10].
  • Sum is 5 + 5 + 10 + 10 = 30.

Constraints:

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10⁹
• 1 <= k <= arr.length

Solution

To solve this problem, we can use dynamic programming. The idea is to keep track of the maximum sum possible for every position in the array by partitioning the array into valid subarrays of length up to k. For each position, we consider all possible partitions ending at that position, calculate the possible sums, and store the maximum sum.

This approach ensures we find the optimal partitioning by considering all possible subarray lengths at each step. The dynamic programming approach is effective here as it allows us to build the solution for larger subarrays using solutions for smaller subarrays, ensuring we always use the best possible partitions to maximize the sum.

Step-by-Step Algorithm

1. Initialize Variables:

   • Create an integer array dp of size n + 1 (where n is the length of the input array arr), initialized to 0.

2. Iterate through the array:

   • For each position i from 1 to n:
     • Initialize a variable maxElement to 0. This variable keeps track of the maximum element in the current partition.
     • Iterate through possible partition lengths j from 1 to k:
       • If i - j is non-negative (to ensure the partition is valid):
         • Update maxElement to be the maximum of maxElement and arr[i - j].
         • Update dp[i] to be the maximum of dp[i] and dp[i - j] + maxElement * j.

3. Return Result:

   • Return dp[n] which contains the maximum sum after partitioning the array.

Algorithm Walkthrough

Let's walk through the algorithm using the example array [1, 3, 7, 9, 2] with k = 2.

1. Initialization:

   • arr = [1, 3, 7, 9, 2]
   • k = 2
   • n = 5
   • dp = [0, 0, 0, 0, 0, 0] (Array initialized to zeros, size n + 1)

2. Iterating through the array:

   • For i = 1:

     • maxElement = 0
     • For j = 1 (since k = 2):
       • i - j = 1 - 1 = 0 (valid partition)
       • maxElement = max(0, arr[0]) = max(0, 1) = 1
       • dp[1] = max(dp[1], dp[0] + maxElement * j) = max(0, 0 + 1 * 1) = 1
     • dp = [0, 1, 0, 0, 0, 0]

   • For i = 2:

     • maxElement = 0
     • For j = 1:
       • i - j = 2 - 1 = 1 (valid partition)
       • maxElement = max(0, arr[1]) = max(0, 3) = 3
       • dp[2] = max(dp[2], dp[1] + maxElement * j) = max(0, 1 + 3 * 1) = 4
     • For j = 2:
       • i - j = 2 - 2 = 0 (valid partition)
       • maxElement = max(3, arr[0]) = max(3, 1) = 3
       • dp[2] = max(dp[2], dp[0] + maxElement * j) = max(4, 0 + 3 * 2) = 6
     • dp = [0, 1, 6, 0, 0, 0]

   • For i = 3:

     • maxElement = 0
     • For j = 1:
       • i - j = 3 - 1 = 2 (valid partition)
       • maxElement = max(0, arr[2]) = max(0, 7) = 7
       • dp[3] = max(dp[3], dp[2] + maxElement * j) = max(0, 6 + 7 * 1) = 13
     • For j = 2:
       • i - j = 3 - 2 = 1 (valid partition)
       • maxElement = max(7, arr[1]) = max(7, 3) = 7
       • dp[3] = max(dp[3], dp[1] + maxElement * j) = max(13, 1 + 7 * 2) = 15
     • dp = [0, 1, 6, 15, 0, 0]

   • For i = 4:

     • maxElement = 0
     • For j = 1:
       • i - j = 4 - 1 = 3 (valid partition)
       • maxElement = max(0, arr[3]) = max(0, 9) = 9
       • dp[4] = max(dp[4], dp[3] + maxElement * j) = max(0, 15 + 9 * 1) = 24
     • For j = 2:
       • i - j = 4 - 2 = 2 (valid partition)
       • maxElement = max(9, arr[2]) = max(9, 7) = 9
       • dp[4] = max(dp[4], dp[2] + maxElement * j) = max(24, 6 + 9 * 2) = 24
     • dp = [0, 1, 6, 15, 24, 0]

   • For i = 5:

     • maxElement = 0
     • For j = 1:
       • i - j = 5 - 1 = 4 (valid partition)
       • maxElement = max(0, arr[4]) = max(0, 2) = 2
       • dp[5] = max(dp[5], dp[4] + maxElement * j) = max(0, 24 + 2 * 1) = 26
     • For j = 2:
       • i - j = 5 - 2 = 3 (valid partition)
       • maxElement = max(2, arr[3]) = max(2, 9) = 9
       • dp[5] = max(dp[5], dp[3] + maxElement * j) = max(26, 15 + 9 * 2) = 33
     • dp = [0, 1, 6, 15, 24, 33]

3. Return Result:

   • dp[5] = 33

The final result is 33.

Code

public class Solution {

  // Method to find the maximum sum after partitioning
  public int maxSumAfterPartitioning(int[] arr, int k) {
    int n = arr.length;
    int[] dp = new int[n + 1]; // Dynamic programming array to store results

    // Iterate through the array
    for (int i = 1; i <= n; i++) {
      int maxElement = 0; // To keep track of the maximum element in the current partition
      // Check partitions of length 1 to k
      for (int j = 1; j <= k && i - j >= 0; j++) {
        maxElement = Math.max(maxElement, arr[i - j]); // Update the maximum element
        dp[i] = Math.max(dp[i], dp[i - j] + maxElement * j); // Update the dp array with the maximum sum
      }
    }
    return dp[n]; // Return the maximum sum after partitioning
  }

  // Main method to test the algorithm
  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    int[] arr1 = { 1, 3, 7, 9, 2 };
    int k1 = 2;
    System.out.println(sol.maxSumAfterPartitioning(arr1, k1)); // Output: 33

    // Example 2
    int[] arr2 = { 4, 8, 1, 6, 5 };
    int k2 = 3;
    System.out.println(sol.maxSumAfterPartitioning(arr2, k2)); // Output: 36

    // Example 3
    int[] arr3 = { 2, 5, 10, 1 };
    int k3 = 2;
    System.out.println(sol.maxSumAfterPartitioning(arr3, k3)); // Output: 30
  }
}

Complexity Analysis

• Time Complexity: The time complexity of the algorithm is , where (n) is the length of the array and (k) is the maximum partition size. This is because for each element in the array, we are considering up to (k) previous elements to determine the optimal partition.

• Space Complexity: The space complexity of the algorithm is , where (n) is the length of the array. This is due to the additional space required for the dynamic programming array dp that stores the results of subproblems.