力扣---1043. 分隔数组以得到最大和

 给你一个整数数组 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 <= 500
• 0 <= arr[i] <= 109
• 1 <= 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];
    }
}