Partition Array for Maximum Sum

The problem asks us to partition the array into contiguous subarrays of length at most k. After partitioning, each subarray’s values will be changed to become the maximum value of that subarray. We need to return the largest sum of the given array after partitioning.

Solution

We can solve this problem using dynamic programming. We’ll create a DP array dp of size n, where dp[i] represents the maximum sum for the subarray arr[0], arr[1], ..., arr[i].

  1. Initialization: Initialize dp[0] = arr[0].
  2. Loop Through the Array: For each i from 1 to n-1, compute dp[i] as the maximum value by considering all possible subarray lengths from 1 to k ending at i.
  3. Result: The result will be in dp[n-1].
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

        for i in range(1, n):
            max_val = 0
            # Loop through the previous k elements to find the best partition
            for j in range(1, min(i + 1, k) + 1):
                max_val = max(max_val, arr[i - j + 1])
                dp[i] = max(dp[i], (dp[i - j] if i >= j else 0) + max_val * j)

        return dp[n - 1]

Explanation

  • max_val keeps track of the maximum value in the last j elements.
  • We multiply max_val with j and add it to the DP value at i - j.
  • We repeat this for all j from 1 to k, and take the maximum.

The time complexity of this solution is O(n * k), where n is the length of the array and k is the given parameter. The space complexity is O(n), considering the DP array storage.