Problem 1043

(Last updated: )

Question statement

Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray. Return the largest sum of the given array after partitioning.

Solution

From the first hint, it was clear to me that I had to use a 1-d dp approach.

Main idea

So let’s initialize a dp array with the intention to store the answer for position i at dp[i]. That is to say, dp[i] will store the largest sum after partitioning nums[:i+1]. Certainly dp[0] = nums[0]. Then the logic is as follows: Suppose we are at nums[i]. Then one of the $k-$ possible scenarios must happen

  • Case 1: nums[i] must be alone in its own contiguous array cur, the resulting group will have a total of max(nums[i:i+1])*len(cur)
  • Case 2: nums[i] gets grouped with nums[i-1], the resulting group will have a total of max(nums[i-1:i+1])*len(cur)
  • …
  • Case k: nums[i] gets grouped with the previous k-1 terms, the resulting group will have a total of max(nums[i-k+1:i+1])*len(cur)

Moreover, to each of these cases, we need to add the sum from the partitions that existed before cur, but this value for case $j$ is stored in $dp[i-j-1]$

So $dp[i] = \texttt{$\max_j$ dp[i-j-1] + $\max$(nums[i-k+1:i+1])*len(cur)}$

One bit of optimization: Instead of computing the max each term (which could in the worst case be an O(n) computation), as $j$ changes, we keep track of the max candidate, and update that value when we find a better candidate.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
    dp = [0 for _ in range(len(arr))]
    dp[0] = arr[0]
    for i in range(1, len(arr)):
        step = 1
        max_elt = arr[i]
        cur = arr[i]+dp[i-1]
        while(step < k and i-step >= 0):
            if(arr[i-step] >= max_elt):
                max_elt = arr[i-step]
            if(dp[i-(step+1)] + max_elt*(step+1) >= cur):
                cur = dp[i-(step+1)] + max_elt*(step+1)
            step +=1
        dp[i] = cur
    return dp[-1]

Comments:

Time complexity: O(n*k) where n=len(nums)

At the time of submission, the above solution passes leetcode submission cases in 162ms, beating 97.76% of users. It uses 16.5MB of memory, beating 84.70% of users.