1210. Partition Array for Maximum Sum

Given an array arr and an integer k, partition it into contiguous subarrays of length at most k. After partitioning, every value in a subarray becomes that subarray's maximum. Return the largest possible sum of the resulting array. The input is JSON {arr, k}.

Input: JSON {arr, k}.

Output: Integer — the maximum sum after partitioning.

Examples

Input: {"arr":[1,15,7,9,2,5,10],"k":3}
Output: 84
Explanation: Partition to maximize each block's max.

Input: {"arr":[1],"k":1}
Output: 1
Explanation: Single element.

Input: {"arr":[1,4,1,5,7,3,6,1,9,9,3],"k":4}
Output: 83
Explanation: Optimal partitioning.

Constraints

• 1<=n<=500
• 1<=k<=n

Asked by