Skip to main content

1043. Partition Array for Maximum Sum

medium

Partition the array into contiguous chunks of length at most k; each chunk becomes its max value. Maximize the resulting sum. Standard 1D DP — listed here as a fixture in the partition-DP family.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray. Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.

Constraints

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

Examples

Example 1

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

Explanation: arr becomes [15,15,15,9,10,10,10]

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i] = max sum of arr[0..i-1] after optimal partitioning.

Hint 2

Transition: dp[i] = max over j in [max(0, i-k), i-1] of dp[j] + max(arr[j..i-1]) * (i - j).

Hint 3

Track the running max over the inner window as you sweep j from i-1 down to i-k. O(n * k) time.

Hint 4

Base: dp[0] = 0.

Solution approach

Reveal approach

Bottom-up 1D DP. dp[i] is the maximum sum achievable using the first i elements after optimal partitioning. For each i from 1 to n, try every chunk-end choice: the last chunk has length L in 1..k, so it covers arr[i-L..i-1]. Compute its max value on the fly by iterating L from 1 to min(k, i) while tracking the running max; then dp[i] = max over L of dp[i-L] + runningMax * L. Base dp[0] = 0. Return dp[n]. Time O(n * k). The 'running max within window' trick avoids precomputing all interval maxes.

Complexity

Time
O(n * k)
Space
O(n)

Related patterns

  • dynamic-programming
  • partition-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Partition Array for Maximum Sum and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →