Domain 2MediumMEDIUM

Partition Array for Maximum Sum

LeetCode problem 1043: Partition Array for Maximum Sum (medium).

Domain: medium•Updated: 2026-09-07
#Dynamic Programming

Problem Breakdown

We are given an integer array arr and an integer k. The goal is to partition this array into contiguous subarrays where each subarray has a length of at most k. Once we make these partitions, every element within a specific subarray gets replaced by the maximum value found in that same subarray. We need to find the configuration of partitions that results in the largest possible total sum after replacement.

Inputs:

  • arr: List of integers (length up to 500).
  • k: Integer representing max partition length (1 <= k <= arr.length).

Outputs:

  • An integer representing the maximum achievable sum.

Implicit Constraints & Edge Cases:

  • Overflow: While standard languages might overflow with N=500N=500 and values up to 10910^9, Python handles large integers automatically, so we don’t need explicit modulo arithmetic or 64-bit checks unless specified by a specific language constraint (which isn’t here).
  • Single Element: If arr has length 1, the answer is simply that element.
  • k=1: Every partition must be size 1; sum remains unchanged from original array.

Intuition

A brute-force approach would try every possible way to split the array into chunks of valid sizes and calculate the resulting sums for each combination. Since we can choose a cut point at almost any index, this leads to an exponential number of partitions (3N3^N roughly), which is computationally infeasible even for N=50N=50.

This problem exhibits optimal substructure (the solution for arr[0..i] depends on solutions for smaller prefixes) and overlapping subproblems. This signals a Dynamic Programming approach.

Let’s define our state: Let dp[i] be the maximum sum we can achieve using only the first i elements of the array (arr[:i]). To calculate dp[i], we consider all possible valid partitions ending at index i-1. Specifically, if the last partition has length j (where 1≤j≤k1 \le j \le k), it spans from index i-j to i-1. The value contributed by this chunk is its maximum element multiplied by 1. We add this to the best result we could get for the remaining prefix (dp[i-j]).

Approach

  1. Initialize a DP array of size N+1N+1 (where NN is length of arr) with zeros. dp[0] = 0 represents an empty partition having sum 0.
  2. Iterate through each index i from 1 to NN. This represents the prefix ending at current position in our DP state.
  3. For every i, iterate backwards for a window length j ranging from 1 up to k.
  4. Maintain a running maximum of elements within the current backward-looking window (arr[i-j] through arr[i-1]).
  5. Update dp[i]: The candidate sum is dp[i-j] + max_window_value. We take the maximum over all valid js for this specific i.
  6. Return dp[N], which holds the answer for the full array length.

Complexity Analysis

  • Time Complexity: O(N⋅K)O(N \cdot K). In our inner loop, we iterate up to k times for each of the N positions in the outer loop. Since KK can be at most NN, worst-case complexity is O(N2)O(N^2). Given constraints (N=500N=500), this results in roughly 250,000 operations, which easily fits within typical time limits (usually ~1 second for ≈108\approx 10^8 ops).
  • Space Complexity: O(N)O(N) to store the DP array.

Solution

def maxSumAfterPartitioning(arr: list[int], k: int) -> int:
    n = len(arr)
    
    # dp[i] stores the maximum sum for the prefix arr[:i] (first i elements)
    # Initialize with 0, size is N+1 to handle base case of empty array easily
    dp = [0] * (n + 1)

    # Iterate through each position from 1 to n representing the end index of a partition
    for i in range(1, n + 1):
        current_max_val = -float('inf')
        
        # Look back up to k elements ending at this position 'i' (exclusive in slice)
        # The window is arr[i-j] ... arr[i-1], length j
        for j in range(1, min(i + 1, k + 1)): 
            current_max_val = max(current_max_val, arr[i - j])
            
            # Calculate potential sum if the last partition has length 'j'
            dp[i] = max(dp[i], dp[i - j] + current_max_val)

    return dp[n]

Edge Cases Handled

  • Single Element Array: The loop runs once, k is at least 1. Logic correctly returns the single element value as sum of partition size 1.
  • Large Values (10910^9): Python’s arbitrary precision integers prevent overflow during summation without manual checks.
  • Small k (e.g., k=1): The inner loop range restricts j to only 1, effectively preventing any merging of elements and returning the sum of original array values.