Partition Array for Maximum Sum
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
You are given an integer array arr and an integer k. Split arr into contiguous blocks, each of length at most k.
After the split, every element of a block is replaced by that block's maximum. Return the largest possible sum of the array after this replacement.
Examples
Input: arr = [2,6,1,3], k = 2 Output: 18
Split as [2,6] | [1,3] to get [6,6,3,3], which sums to 18.
Input: arr = [4,1,1,1], k = 4 Output: 16
Keep the whole array together so every element becomes 4: 16.
Input: arr = [5], k = 1 Output: 5
A single element stays as it is.
Constraints
- 1 <= len(arr) <= 500
- 0 <= arr[i] <= 10^6
- 1 <= k <= len(arr)
Approaches
- Try every split — time O(2^n · n), space O(n)
Follow-up
The DP only needs the last k values of best, so the space can drop to O(k) with a ring buffer. The use cases keep the "choose the last block" structure but change what a block is worth: the minimum instead of the maximum with the sum minimized, and a cost of one maximum per block.
Related problems
Start free on Cariara · Coding problems · System design studio
