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