给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
示例 1：
输入：arr = [1,15,7,9,2,5,10], k = 3 输出：84 解释：数组变为 [15,15,15,9,10,10,10]
示例 2：
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4 输出：83
示例 3：
输入：arr = [1], k = 1 输出：1
提示：
1 <= arr.length <= 5000 <= arr[i] <= 1091 <= k <= arr.length
题目有点绕，实际上就是给你一个数组，你可以将这个数组分成长度最大不超过 k 的若干个连续的子数组，并用这些子数组中的最大值代替其他的元素，求代替之后所有元素之和的最大值。
可以想到，第 i 个位置的最大值可以由它前面 k 个对应位置的最大值加上这段数组中的最大值乘以出现次数来得出。
当 k 等于 2 时，实际上就变成了爬楼梯。
k 等于其他数时，就是一次能爬更多台阶的爬楼梯。
class Solution { public int maxSumAfterPartitioning(int[] arr, int k) { int len = arr.length; // 动态规划数组 int[] dp = new int[len + 1]; for (int i = 1; i <= len; i ++) { int max = arr[i - 1]; // 由于是将中间位置的最大值全部添到中间数组中，从后往前不会错过当前的最大值。 for (int j = 1; j <= k; j ++) { if (i - j >= 0) { max = Math.max(max, arr[i - j]); dp[i] = Math.max(dp[i], dp[i - j] + max * j); } } } return dp[len]; } }
