#1043

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Partition Array for Maximum Sum

Partition an array into subarrays of length at most k, replacing each with its maximum to maximize total sum efficiently.

array dynamic programming

Problem Statement

Given an integer array arr and an integer k, partition the array into contiguous subarrays of length at most k. Replace all elements in each subarray with the maximum value of that subarray.

Return the largest possible sum of the transformed array after partitioning. The array length and values ensure the result fits within a 32-bit integer. For example, arr = [1,15,7,9,2,5,10] with k = 3 becomes [15,15,15,9,10,10,10] yielding sum 84.

Examples

Example 1

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

Output: 84

arr becomes [15,15,15,9,10,10,10]

Example 2

Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4

Output: 83

Example details omitted.

Example 3

Input: arr = [1], k = 1

Output: 1

Example details omitted.

Constraints

1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length

Solution Approach

Dynamic Programming State Definition

Define dp[i] as the maximum sum for the first i elements of arr. This transforms the problem into a state transition DP, where each dp[i] depends on previous dp[j] for j < i.

Iterative State Transition

For each position i, consider all possible subarray lengths from 1 to k ending at i. Track the maximum value within the subarray and update dp[i] = max(dp[i], dp[i-len] + maxVal*len), ensuring the DP accounts for all partitions efficiently.

Final Computation

After iterating through the array, dp[n] holds the largest sum after optimal partitioning. Using O(N*K) time and O(N) space avoids recomputation and correctly handles the subarray max replacements.

Complexity Analysis

Metric	Value
Time	O(N \cdot K)
Space	O(N)

Time complexity is O(N*K) because each element considers up to k previous subarray lengths. Space complexity is O(N) to store dp values for all positions. This handles array sizes up to 500 efficiently without unnecessary recomputation.

What Interviewers Usually Probe

Focus on defining dp[i] correctly and explaining why previous dp values are reused.
Expect reasoning about how subarray length limits (k) influence state transitions.
Look for explanation of why maximum value in each partition maximizes the sum.

Common Pitfalls or Variants

Common pitfalls

Confusing subarray length with number of partitions leads to incorrect dp indices.
Failing to update maximum within each subarray for the current length.
Using nested loops incorrectly, causing O(N^2) when k is large, instead of O(N*K).

Follow-up variants

Change the problem to minimize sum by using subarray minimums instead of maximums.
Allow non-contiguous partitions, requiring different DP or greedy strategies.
Add a constraint on the number of partitions, combining partition count with sum maximization.

FAQ

What is the main pattern used in Partition Array for Maximum Sum?

State transition dynamic programming is the core pattern, where dp[i] stores the maximum sum for the first i elements considering subarrays up to length k.

Can k equal the array length in this problem?

Yes, k can range from 1 to the length of arr, allowing the entire array to form one subarray if k equals arr.length.

How do I compute the maximum value for each subarray efficiently?

Within the DP iteration, track the maximum value dynamically while expanding the subarray length up to k to avoid recomputation.

What are the constraints on arr and k?

The array length is 1 to 500, elements range from 0 to 10^9, and k is between 1 and arr.length.

Why is DP necessary instead of a greedy approach?

Greedy fails because local maximums may not yield the global maximum sum; DP correctly considers all partitions ending at each index.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ to represent the maximum element sum of the first $i$ elements of the array after separating them into several subarrays. At the beginning, $f[i]=0$, and the answer is $f[n]$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        f = [0] * (n + 1)
        for i in range(1, n + 1):
            mx = 0
            for j in range(i, max(0, i - k), -1):
                mx = max(mx, arr[j - 1])
                f[i] = max(f[i], f[j - 1] + mx * (i - j + 1))
        return f[n]

Continue Practicing

#1039 minimum score triangulation of polygon #1048 longest string chain #1049 last stone weight ii