AlgoViz
HomeDynamic Programming

Partition Array for Maximum Sum

Medium

Try every group length ending here

Problem

Partition an array into contiguous groups of length at most k, replacing each group with its max*size. Maximize the sum.

In simple words

Try ending the last group at each of the previous k spots, replacing it with its max value times its size.

The idea

For each position, look back up to k elements forming the last group, taking that group's maximum times its length plus the best answer before it. Tracking the running maximum inside the inner loop keeps each step O(1).

The trick

  • Track the group maximum as the inner loop extends backwards.
  • Group contribution = maxInGroup × groupLength.
  • O(n·k).

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
15
7
9
2
5
10
0
1
2
3
4
5
6

Step 1 of 2. Here's the example — arr=[1,15,7,9,2,5,10], k=3 Values: 1, 15, 7, 9, 2, 5, 10.

1/2
Optimal
timeO(n*k)spaceO(n)
1dp[i]=max over len 1..k of dp[i-len]+max(last len)*len

Input

array
[1, 15, 7, 9, 2, 5, 10]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 15, 7, 9, 2, 5, 10], k = 3
Output:
84
Explanation:
Grouping and maxing each part gives 84.

Example 2

Input:
nums = [1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3], k = 4
Output:
83
Explanation:
Best partition total is 83.

Example 3

Input:
nums = [1], k = 1
Output:
1
Explanation:
One element → 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.