Partition Array for Maximum Sum
Given an integer array arr and an integer k, partition the array into contiguous subarrays of length at most k. After partitioning, every element of a subarray is replaced by the maximum value in that subarray. Return the largest sum the modified array can reach.
Input & Output
Input
arr — the array to partition
k — the maximum length of each contiguous subarray
Output
the largest possible sum of the array after each subarray is flattened to its maximum
Example
Input
arr = [1, 15, 7, 9, 2, 5], k = 3
Output
72
Explanation
Split into [1, 15, 7] and [9, 2, 5]. The first becomes [15, 15, 15] and the second becomes [9, 9, 9], for 45 + 27 = 72. Splitting instead into [1], [15, 7, 9], [2, 5] gives only 1 + 45 + 10 = 56.
Example
Input
arr = [1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3], k = 4
Output
83
Explanation
The best split is [1, 4], [1, 5, 7], [3, 6, 1, 9], [9, 3], contributing 4×2 + 7×3 + 9×4 + 9×2 = 8 + 21 + 36 + 18 = 83. Cutting into equal blocks of four instead — [1, 4, 1, 5], [7, 3, 6, 1], [9, 9, 3] — reaches only 20 + 28 + 27 = 75, so the group sizes have to vary.
Constraints
1 <= arr.length <= 5000 <= arr[i] <= 10^91 <= k <= arr.length