题目描述
给定 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]; }