Partition Array for Maximum Sum

Medium20–25 min

Topics

Dynamic Programming

Companies

AmazonGoogleBloomberg

Cut an array into contiguous groups, each no longer than `k`, then replace every element of a group with that group's own largest value. Choose the grouping that makes the total, after every replacement, as large as possible. Once a group's length is fixed, its contribution is fixed too — the group's maximum, counted once per element in it — so the only real decision at each position is how long the next group should run, from 1 up to k. Reaching some position i for the first time as the start of a fresh group means an earlier position was already settled optimally, and the stretch between them is exactly one new group. So the best total ending at i is the best total ending at some valid earlier cut, plus that new group's contribution — and trying every legal group length at every position, building left to right, means every earlier answer needed is already on hand.

Test Case 1:

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

Output:84

Explanation:Grouping as [1,15,7] | [9] | [2,5,10] replaces each group with its max: 15+15+15 + 9 + 10+10+10 = 45 + 9 + 30 = 84 — the best of every grouping choice up to length 3.

Test Case 2:

Input:arr = [1,2,3], k = 1

Output:6

Explanation:With k = 1 every group is exactly one element, so nothing ever changes — the answer is always just the sum of the original array.

Test Case 3:

Input:arr = [1], k = 15

Output:1

Explanation:A single element can only ever form a group of size 1, no matter how large k is allowed to be.

Constraints

◆1 ≤ arr.length ≤ 10
◆1 ≤ k ≤ arr.length
◆1 ≤ arr[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursion Without Memoization

Brute

From whatever position is next unpartitioned, the only choice that matters is how long the next group is — anywhere from 1 up to k elements (fewer if the array runs out first). Once that length is picked, every element in that stretch contributes the same amount: the stretch's own maximum, repeated once per element in it. Try every legal length, add what the rest of the array can best achieve after that group ends, and keep the best total. Written this way the recursion is short, but the same starting position gets re-entered through many different combinations of earlier group lengths, so the same subproblem is re-solved again and again.

TimeO(kⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] arr;
    private int k;
    public int maxSumAfterPartitioning(int[] arr, int k) {
        this.arr = arr;
        this.k = k;
        return solve(0);
    }
    private int solve(int i) {
        if (i == arr.length) return 0;
        int best = 0;
        int curMax = 0;
        for (int len = 1; len <= k && i + len <= arr.length; len++) {
            curMax = Math.max(curMax, arr[i + len - 1]);
            int candidate = curMax * len + solve(i + len);
            if (candidate > best) best = candidate;
        }
        return best;
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Work left to right instead of recursing: dp[i] holds the best total achievable using just the first i elements. To extend from some earlier dp[i-len] to dp[i], the newest group is exactly those last `len` elements, contributing `len` copies of their maximum. Every dp value needed to compute dp[i] — for every group length from 1 up to k — was already finalized on an earlier iteration, so nothing is ever recomputed. The running maximum for the current group can be tracked incrementally as `len` grows, so no extra scan is needed to find it.

TimeO(n·k)