Partition Array for Maximum Sum

Medium
1053.

Partition Array for Maximum Sum

Partition Array for Maximum Sum is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and HCL interviews.

Partition arr into contiguous subarrays of length at most k. After partitioning, every value in a subarray becomes that subarray's maximum.

Return the largest possible sum of the resulting array.

Example 1

Input
arr = [1,15,7,9,2,5,10], k = 3
Output
84
Explanation
`[15,15,15,9,10,10,10]` sums to 84.

Example 2

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

Example 3

Input
arr = [1], k = 1
Output
1

Constraints

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 10^9
  • 1 <= k <= arr.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var maxSumAfterPartitioning = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Partition Array for Maximum Sum — Problem & Solution

Partition Array for Maximum Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Partition Array for Maximum Sum is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and HCL interviews.

Problem statement

Partition arr into contiguous subarrays of length at most k. After partitioning, every value in a subarray becomes that subarray's maximum.

Return the largest possible sum of the resulting array.

Example 1

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: `[15,15,15,9,10,10,10]` sums to 84.

Example 2

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

Example 3

Input: arr = [1], k = 1
Output: 1

Constraints

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 10^9
  • 1 <= k <= arr.length

Hints for Partition Array for Maximum Sum

  1. Hint 1

    dp[i] = the best sum for the first i elements.

  2. Hint 2

    The last subarray ends at i-1 and has some length from 1 to k.

  3. Hint 3

    Extend that last subarray leftwards, keeping its running maximum as you go.

How to solve Partition Array for Maximum Sum

Prefix DP. dp[i] is the best total for arr[0..i-1]. The final subarray has length len between 1 and k; extending it leftwards lets you keep its maximum in a running variable, so each candidate is dp[i-len] + max · len.

Approach

  1. Set dp[0] = 0.
  2. For each i from 1 to n, walk len from 1 to min(k, i), updating peak = max(peak, arr[i-len]).
  3. Take the best dp[i-len] + peak · len.

Why it works

Growing the last block leftwards is what makes the inner loop O(1) per step: the maximum of a window that only ever extends is a single running comparison, so no separate max query is needed. Trying to be greedy — always cutting at the largest value — fails, because a small value is often worth absorbing into a block so that a nearby large value is multiplied more times.

Complexity

  • Time — O(n · k)
  • Space — O(n)

Pitfalls

  • Subarrays have length at most k, not exactly k.
  • The running maximum must reset for each i; carrying it across resets inflates earlier blocks.
  • Values reach 10⁹ and blocks reach length k, so the running sum needs 64 bits at the upper bound.

Reference solution

Python

from typing import List

def maxSumAfterPartitioning(arr: List[int], k: int) -> int:
    n = len(arr)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        peak = 0
        best = 0
        for length in range(1, min(k, i) + 1):
            peak = max(peak, arr[i - length])
            best = max(best, dp[i - length] + peak * length)
        dp[i] = best
    return dp[n]

Java

public static int maxSumAfterPartitioning(int[] arr, int k) {
    int n = arr.length;
    long[] dp = new long[n + 1];
    for (int i = 1; i <= n; i++) {
        long best = 0;
        long peak = 0;
        for (int len = 1; len <= k && len <= i; len++) {
            peak = Math.max(peak, arr[i - len]);
            best = Math.max(best, dp[i - len] + peak * len);
        }
        dp[i] = best;
    }
    return (int) dp[n];
}

C++

int maxSumAfterPartitioning(vector<int>& arr, int k) {
    int n = (int) arr.size();
    vector<long long> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long best = 0, peak = 0;
        for (int len = 1; len <= k && len <= i; len++) {
            peak = max(peak, (long long) arr[i - len]);
            best = max(best, dp[i - len] + peak * len);
        }
        dp[i] = best;
    }
    return (int) dp[n];
}

JavaScript

var maxSumAfterPartitioning = function(arr, k) {
    var n = arr.length, i;
    var dp = [];
    for (i = 0; i <= n; i++) dp.push(0);
    for (i = 1; i <= n; i++) {
        var best = 0, peak = 0;
        for (var len = 1; len <= k && len <= i; len++) {
            if (arr[i - len] > peak) peak = arr[i - len];
            var cand = dp[i - len] + peak * len;
            if (cand > best) best = cand;
        }
        dp[i] = best;
    }
    return dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming