Partition Array for Maximum Sum

给一个数组和一个数字k, 可以有一种操作, 把k个数组变成最大的数字. 求最大的数组.

这题动态规划直接做, 然后注意一下边界.

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        int res = 0;
        for(int i = 0; i <= n; i++) {
            int max = 0;
            int t = Math.max(0, i - k);
            for(int j = i - 1; t <= j; j--) {
                max = Math.max(max, arr[j]); 
                dp[i] = Math.max(dp[i], dp[j] + max * (i - j)); // dp[i - 1] dp[i - 2]
            }
        }
        return dp[n];
    }
}