最大 m 段和

题目描述

给定 n 个整数组成的序列，将其分割为 m 段，每段子序列中的数在原序列中连续排列，如何分割才能使这 m 段子序列的和的最小值最大？

代码

    public static int solve(int[] array, int n) {
        int length = array.length;
        if (length == 0) {
            return 0;
        }
        int[][] dp = new int[length + 1][n + 1];
        for (int i = 0; i < length; i++) { // i 个数分成一份
            dp[i + 1][1] = dp[i][1] + array[i];
        }
        for (int i = 1; i <= length; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= length; i++) {
            for (int j = 2; j <= n; j++) {
                int max = 0;
                for (int k = 1; k < i; k++) {
                    max = Math.max(max, Math.min(dp[i][1] - dp[k][1], dp[k][j - 1])); // dp[i][j] = max(min(dp[i][1] - dp[k][1], dp[k][j-1]))
                }
                dp[i][j] = max;
            }
        }
        return dp[length][n];
    }