#1043
Partition Array for Maximum Sum
pupil · 470 · lc medium +26 · verified · 77.3% accepted · 5,043 likes · top 88%
Description
Given an integer array arr and integer k, partition arr into contiguous subarrays each of length at most k. All values in each subarray are then set to that subarray's maximum value.
Return the largest possible total sum of the transformed array. Answers fit in a 32-bit integer.
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
Code
1
2
3