410. 分割数组的最大值
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：
输入：nums = [1,4,4], m = 3
输出：4
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= m <= min(50, nums.length)
解决办法一： 动态规划
枚举所有的分割点, 将数组分成[0, k], [k+1, n]两个部分。其中[0,k]部分需要递归的计算将它分成m-1份的最大值。状态转移方程如下：
[f[i][j]=min _{k=0}{max (f[k][j-1], s u b(k+1, i))}
]
可使用数据记录已经求得的状态。
递归写法如下：
private int[][] f;
private int[] sub;
public int splitArray(int[] nums, int m) {
int n = nums.length;
// f数据作为动态规划的记忆数组
// f[i][j] 表示数据k的[0,i]部分分成j部分的最大值
this.f = new int[n][m + 1];
for (int i = 0; i < n; i++) {
Arrays.fill(f[i], Integer.MAX_VALUE);
}
// sub数组用于表示前缀和
this.sub = new int[n];
sub[0] = nums[0];
for (int i = 1; i < n; i++) {
sub[i] = sub[i-1] + nums[i];
}
return splitArray(nums, n-1, m);
}
private int splitArray(int[] nums, int k, int m) {
if (m == 1) {
return sub[k];
}
if (f[k][m] != Integer.MAX_VALUE) {
return f[k][m];
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) {
if (i + 1 >= m - 1) {
// if条件确保分割的时候, 不会出现空数组
int kValue = splitArray(nums, i, m - 1);
res = Math.min(res, Math.max(kValue, sub[k] - sub[i]));
}
}
f[k][m] = res;
return res;
}
迭代写法如下：
迭代写法就是填一张f[i][j]的二维表格。填表格的规则就在状态转移方程当中。
public int splitArray(int[] nums, int m) {
int n = nums.length;
// f数据作为动态规划的记忆数组
// f[i][j] 表示数据k的[0,i]部分分成j部分的最大值
int[][] f = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(f[i], Integer.MAX_VALUE);
}
// sub数组用于表示前缀和
int[] sub = new int[n + 1];
for (int i = 0; i < n; i++) {
sub[i + 1] = sub[i] + nums[i];
}
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(i, m); j++) {
for (int k = 0; k < i; k++) {
f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
}
}
}
return f[n][m];
}
方法二： 贪心 + 二分法
贪心地模拟分割的过程，从前到后遍历数组，用 sum 表示当前分割子数组的和，cnt 表示已经分割出的子数组的数量（包括当前子数组），那么每当 sum 加上当前值超过了 x，我们就把当前取的值作为新的一段分割子数组的开头，并将 cnt 加 1。遍历结束后验证是否 cnt 不超过 m。
如果不超过m, 则说明当前的x太大了(也可能是刚刚好)。如果超过m, 则说明当前的x 太小了。这就是二分的原则。
class Solution {
public int splitArray(int[] nums, int m) {
// left值为在数组每个元素是一份的情况, 也就是数组元素最大值
// right值为把数组全部作为一份的情况, 也就是数组所有元素和
int left = 0, right = 0;
for (int i = 0; i < nums.length; i++) {
right += nums[i];
if (left < nums[i]) {
left = nums[i];
}
}
while (left < right) {
int mid = (right - left) / 2 + left;
// 以每组最大值不超过mid值来分, 看m份是不是够分
if (check(nums, mid, m)) {
// 这是够分的情况, 表示mid值还是可能太大了
right = mid;
} else {
// 这是不够分的情况
left = mid + 1;
}
}
return left;
}
public boolean check(int[] nums, int x, int m) {
int sum = 0;
// 对组数技术
int cnt = 1;
for (int i = 0; i < nums.length; i++) {
// 每次sum加到不能在加为止, 因为再加就会超过上限值x
if (sum + nums[i] > x) {
cnt++;
sum = nums[i];
} else {
sum += nums[i];
}
}
// 判断将所有元素加完之后, 已有的分组是否超过m, 如果不超过m, 则说明mid值太大了。
// 如果大于m, 说明当前的mid值一定是不符合条件的, 因为太小了
return cnt <= m;
}
}