#694 · #1043 · Partition Array for Maximum Sum(分隔数组以得到最大和)

Given an integer array arr and an integer k, partition arr into contiguous subarrays each of length at most k. Every element of a subarray is then replaced by that subarray's maximum. Return the largest possible sum after the transformation. Constraints: 1 <= arr.length <= 500, 0 <= arr[i] <= 10^9, 1 <= k <= arr.length.