Dynamic Programming • Front Partitioning

Partition Array for Maximum Sum

Partition an integer array into contiguous subarrays of length at most k. After partitioning, each element is changed to become the maximum value of that subarray.

Try Interactive Simulator

Overview

This is a classic Front Partitioning problem. We want to find the optimal way to group the last `j` elements into a single partition, where `j` is at most `k`.

The DP State

`dp[i]` represents the maximum sum achievable for the prefix of length `i`. It answers: "What's the best I can do using the first `i` items?"

The Lookback

To compute `dp[i]`, we look BACKWARDS by `j` steps (up to `k`). We assume the items from `i-j` to `i-1` form a new partition. Their contribution is `max_val * j`.

The Recurrence

The total score if we partition the last `j` items is: `dp[i-j] + (max_in_sub * j)`. We take the maximum of this over all valid `j`.

1

15

7

9

DP Array (Max Sum for Prefix)

0

Max In Partition

0

Code Tracker

:::

1let dp = new Array(n + 1).fill(0);

2for (let i = 1; i <= n; i++) {

3 let maxInSub = -Infinity;

4 // Look back up to k elements

5 for (let j = 1; j <= Math.min(i, k); j++) {

6 maxInSub = Math.max(maxInSub, arr[i - j]);

7 let sum = dp[i - j] + maxInSub * j;

8 dp[i] = Math.max(dp[i], sum);

9 }

10}

11return dp[n];

Partition Array Max Sum

Partition Array Max Sum

Partition Array for Maximum Sum

Overview

The DP State

The Lookback

The Recurrence

Partition Array for Maximum Sum

Overview

The DP State

The Lookback

The Recurrence