关于javascript:410-分割数组的最大值

给定一个非负整数数组和一个整数 m，你须要将这个数组分成 m 个非空的间断子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

留神:
数组长度 n 满足以下条件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:

输出:
nums = [7,2,5,10,8]
m = 2

输入:
18

解释:
一共有四种办法将 nums 宰割为 2 个子数组。
其中最好的形式是将其分为 [7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为 18，在所有状况中最小。

一看难度是 hard，霎时慌了有没有，齐全没思路，间接放弃得了。

回头细看题目，将一个数组分为间断的 m 个数组，求子数组各自和的最小值。是不是能够用暴力法，能不能枚举所有的状况？感觉有点难度，状况太多了。

那就先想想特例吧。以示例子中的数组为例，如果 m =n, 即每一项都是一个子数组，那么子数组和的最大值就是 10，也就是数组中的最大值。如果 m =1，那子数组就是本人自身，和的最大值为 32，也就是数组的和。对于 1<m<n 的状况，其子数组和的最大值也就在 10 – 32 之间。

首先，还是应用枚举的办法，假如各子数组和的最大值为 10，咱们尝试为
[7,2,5,10,8] 划分子数组。咱们能够写下以下代码来划分

let min = 10; // 假如最大值为 10
let nums = [7,2,5,10,8];
let childNum = 1; // 子数组个数
let sum = 0; // 记录子数组的和
for(let num of nums){
    // 如果子数组和大于 10，将 sum 置为 0，子数组数加 1
    if(sum > 10) {
        sum = 0;
        childNum++;
    }
    sum += num;
}

这样咱们就能够得出子数组的个数。下面的状况将数组分为了如下四个子数组：

[7,2], [5], [10], [8]

很显然 4 个子数组与题目中传进来的 m = 2 不符，所以 10 就不是咱们要找的值。接下来就能够往后一个个试了。

然而对于这样的状况，是有优化空间的，能够对范畴内的值用二分查找。所以这道题的最终解决方案如下。

var splitArray = function(nums, m) {

if(!nums.length) return null;
let left = right = 0;
// left 为数组最大值，right 为数组的和
for(let num of nums) {left = Math.max(left, num);
    right += num;
}
while(left < right) {
    // 子数组的数量
    let count = 1;
    // 每次重两头值开始尝试
    let mid = ((right - left) >> 1) + left;
    let sum = 0;
    for(let num of nums) {if(sum + num > mid) {
            sum = 0;
            count ++;
        }
        sum += num
    }
    // 子数组过多，下一次尝试大一点的值，否则尝试小一点的值
    if(count > m) {left = mid + 1;} else {right = mid}
}
return left;

};