NeetCode #694LC-1043Medium1-D Dynamic Programming
← Back to All Problems#694 · #1043 · Partition Array for Maximum Sum(分隔数组以得到最大和)
📌 Problem Statement & Constraints
Given an integer array
arr and an integer k, partition arr into contiguous subarrays each of length at most k. Every element of a subarray is then replaced by that subarray's maximum. Return the largest possible sum after the transformation. Constraints: 1 <= arr.length <= 500, 0 <= arr[i] <= 10^9, 1 <= k <= arr.length.💡 Core Algorithmic Approaches
- Let
dp[i]be the maximum transformed sum of the prefixarr[0..i-1]. - The last group of that prefix has some length
jin1..kand contributesj * max(arr[i-j..i-1]). - So
dp[i] = max over j of dp[i-j] + j * running_max, where the running maximum is tracked whilejgrows. - This has optimal substructure because a partition only couples adjacent elements.
💻 Benchmark Python3 Implementation
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
n = len(arr)
dp = [0] * (n + 1)
for i in range(1, n + 1):
best = 0
for j in range(1, min(k, i) + 1):
best = max(best, arr[i - j]) # max over the last j elements
dp[i] = max(dp[i], dp[i - j] + best * j)
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * k): each position extends its last group up to k times.
💾 Space Complexity
O(n): the dp array.
⚠️ Interview Pitfalls & Follow-ups
- Recomputing
max(arr[i-j:i])inside the loop: tracking the running maximum keeps the inner body O(1); recomputing makes it O(n * k^2). - Capping
jatkonly: it must also be capped ati, since a prefix shorter thankcannot end with a longer group. - Seeding
dp[0]with something other than 0: the empty prefix has sum 0. - Assuming every group must have length exactly
k: groups may be shorter, which is why the inner loop runs over allj.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.