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

解法一：动态规划

dp[i] 表示完成前 i 个数的分隔得到的最大值。有以下状态转移方程：

其中，表示原数组下标闭区间 [i,j] 之间的最大值。

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        final int n = arr.length;
        // 下标从1开始
        // maxVal[i][j]表示下标范围[i, j]之间的最大值
        int[][] maxVal = new int[n + 1][n + 1];
        for (int i = n; i >= 1; --i) {
            maxVal[i][i] = arr[i - 1];
            for (int j = i + 1; j <= n; ++j) {
                maxVal[i][j] = Math.max(maxVal[i][j - 1], arr[j - 1]);
            }
        }
        // dp[i]表示完成前i个数的分隔得到的最大值
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = arr[0];
        for (int i = 2; i <= n; ++i) {
            dp[i] = Integer.MIN_VALUE;
            // 防止下标越界
            for (int len = 1; len <= Math.min(i, k); ++len) {
                dp[i] = Math.max(dp[i], dp[i - len] + len * maxVal[i - len + 1][i]);
            }
        }
        return dp[n];
    }
}