Skip to main content

1043. Partition Array for Maximum Sum

medium

Partition an array into contiguous chunks of size at most k. After partitioning, each chunk's value becomes its max element. Maximize the sum.

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,6], 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 using the first i elements. For each i sweep back up to k positions, tracking the chunk's running max.

Hint 2

dp[i] = max over j from 1 to k of dp[i - j] + j * max(arr[i-j..i-1]).

Hint 3

Recompute the running max incrementally as j grows so the inner loop is O(k).

Solution approach

Reveal approach

Define dp[i] as the maximum sum achievable using the first i elements with a valid partitioning. dp[0] = 0. For each i from 1 to n, sweep j from 1 to min(i, k) maintaining a running chunk_max for the trailing j elements. dp[i] = max(dp[i], dp[i - j] + j * chunk_max). Return dp[n]. The trick is computing chunk_max incrementally — when j grows by 1, the new chunk includes one more element at arr[i - j], so chunk_max = max(chunk_max, arr[i - j]). This keeps the inner loop at O(k) instead of O(k^2). Total O(n * k) time, O(n) space.

Complexity

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

Related patterns

  • dynamic-programming

Related problems

Asked at

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

  • Amazon

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →