# 「力扣」第 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
提示：
# 题意分析
各自和的最大值最小，这句话读起来有一点点绕。我们拆分一下：
由于数组是确定的，其中一组分得多，相应地另一组分到的值就少。所以对于任意一种拆分（切成
m段），这m段可以取最大值val；我们需要找到一种拆分，使得这个最大值
val的值是所有分成m段拆分里值最小的那个；具体怎么拆，题目不用我们求，只需要我们计算出val的值。
# 关键字分析
这个题目非常关键的字眼是：非负整数数组、非空 和 连续。尤其是「非负整数数组」和「连续」这两个信息，请读者看完下面分析以后再来体会「连续」为什么那么重要。
# 解题思路的直觉来源
基于「力扣」第 69 题、第 287 题，知道二分查找的应用：可以用于查找一个有范围的 整数，就能想到是不是可以使用二分查找去解决这道问题。
事实上，二分查找最典型的应用我们都见过，《幸运 52》猜价格游戏，主持人说「低了」，我们就应该往高了猜。
这种二分查找的应用大家普遍的叫法是「二分答案」，即「对答案二分」。它是相对于二分查找的最原始形式「在一个有序数组里查找一个数」而言的。
# 挖掘单调性
使用二分查找的一个前提是「数组具有单调性」，我们就去想想第 410 题有没有类似的单调性。「最大值最小」就提示了单调性：
- 如果设置「数组各自和的最大值」很大，那么必然导致分割数很小；
- 如果设置「数组各自和的最大值」很小，那么必然导致分割数很大。
仔细想想，这里「数组各自和的最大值」就决定了一种分割的方法。再联系一下我们刚刚向大家强调的题目的要求 连续 和题目中给出的输入数组的特点: 非负整数数组。
那么，我们就可以通过调整「数组各自和的最大值」来达到：使得分割数恰好为 m 的效果。这里要注意一个问题：
# 注意事项
如果某个 数组各自和的最大值 恰恰好使得分割数为 m ，此时不能放弃搜索，因为我们要使得这个最大值 最小化，此时还应该继续尝试缩小这个 数组各自和的最大值 ，使得分割数超过 m ，超过 m 的最后一个使得分割数为 m 的 数组各自和的最大值 就是我们要找的 最小值。
这里想不太明白的话，可以举一个具体的例子：
例如：（题目中给出的示例）输入数组为 [7, 2, 5, 10, 8] ，m = 2 。如果设置 数组各自和的最大值 为 21，那么分割是 [7, 2, 5, | 10, 8]，此时 m = 2，此时，这个值太大，尝试一点一点缩小：
- 设置 数组各自和的最大值 为
20，此时分割依然是[7, 2, 5, | 10, 8]，m = 2； - 设置 数组各自和的最大值 为
19，此时分割依然是[7, 2, 5, | 10, 8]，m = 2； - 设置 数组各自和的最大值 为
18，此时分割依然是[7, 2, 5, | 10, 8]，m = 2； - 设置 数组各自和的最大值 为
17，此时分割就变成了[7, 2, 5, | 10, | 8]，这时m = 3。
m 变成 3 之前的值 数组各自和的最大值 18 是这个问题的最小值，所以输出 18。
# 代码实现
说明：
- 以下代码实现中采用
while (left < right)的写法表示退出循环以后left == right成立，这种通过「左右边界」向中间逼近，最后得到一个数的二分查找思考路径，我在「力扣」的题解区已经多次向大家介绍，并且强调了使用细节和注意事项，这里就不赘述了； if (splits > m)的反面是splits <= m此时，下一轮搜索区间是[left, mid]，这个时候我们没有排除掉mid这个值，符合我们上面的逻辑：当分割数恰好等于m的时候，尝试缩小 数组各自和的最大值。
参考代码：
public class Solution {
public int splitArray(int[] nums, int m) {
int max = 0;
int sum = 0;
// 计算「子数组各自的和的最大值」的上下界
for (int num : nums) {
max = Math.max(max, num);
sum += num;
}
// 使用「二分查找」确定一个恰当的「子数组各自的和的最大值」，
// 使得它对应的「子数组的分割数」恰好等于 m
int left = max;
int right = sum;
while (left < right) {
int mid = left + (right - left) / 2;
int splits = split(nums, mid);
if (splits > m) {
// 如果分割数太多，说明「子数组各自的和的最大值」太小，此时需要将「子数组各自的和的最大值」调大
// 下一轮搜索的区间是 [mid + 1, right]
left = mid + 1;
} else {
// 下一轮搜索的区间是上一轮的反面区间 [left, mid]
right = mid;
}
}
return left;
}
/***
*
* @param nums 原始数组
* @param maxIntervalSum 子数组各自的和的最大值
* @return 满足不超过「子数组各自的和的最大值」的分割数
*/
private int split(int[] nums, int maxIntervalSum) {
// 至少是一个分割
int splits = 1;
// 当前区间的和
int curIntervalSum = 0;
for (int num : nums) {
// 尝试加上当前遍历的这个数，如果加上去超过了「子数组各自的和的最大值」，就不加这个数，另起炉灶
if (curIntervalSum + num > maxIntervalSum) {
curIntervalSum = 0;
splits++;
}
curIntervalSum += num;
}
return splits;
}
public static void main(String[] args) {
int[] nums = new int[]{7, 2, 5, 10, 8};
int m = 2;
Solution solution = new Solution();
int res = solution.splitArray(nums, m);
System.out.println(res);
}
}
复杂度分析：
- 时间复杂度：
，这里 表示输入数组的长度， 表示输入数组的和，代码在 区间里使用二分查找找到目标元素，而每一次判断分支需要遍历一遍数组，时间复杂度为 ； - 空间复杂度：
，只使用到常数个临时变量。
作者：liweiwei1419 链接：https://suanfa8.com/binary-search/solutions-3/0410-split-array-largest-sum 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。