⚡Flashcard Drill➔
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

  1. Let dp[i] be the maximum transformed sum of the prefix arr[0..i-1].
  2. The last group of that prefix has some length j in 1..k and contributes j * max(arr[i-j..i-1]).
  3. So dp[i] = max over j of dp[i-j] + j * running_max, where the running maximum is tracked while j grows.
  4. 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 j at k only: it must also be capped at i, since a prefix shorter than k cannot 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 all j.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems