410. 分割数组的最大值

[yankewei]

给定一个非负整数数组和一个整数 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，在所有情况中最小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-array-largest-sum

[yankewei]

Go

这种使...最大值最小是二分查找常见的问题，下面来说一下思路：
首先，我们其实是可以找到一个范围的。这个值肯定在max(nums)(数组中最大值)和sum(nums)(数组的和)之间。那么我们肯定可以在这些值之间找到想要的答案。
我们假设max(nums)这个就是我们要找的值，设置一个cnt变量来保存我们已经分了几分数组了，那么我遍历数组，设置一个变量subSum用来保存当前子数组的和，在遍历的时候有两个情况：

• 当subSum=max(nums)时，我们就可以把它分成一份数组。然后subSum归为0，cnt加1
• 当subSum>max(nums)时，说明当前遍历的元素不能再加到当前的子数组中了，否则就大于subSum了，那我们的假设就不成立了，这时应该把当前遍历的元素保存到下一份子数组中，subSum=当前遍历的元素值，cnt加1

我们可以从max(nums)到sum(nums)递增开始尝试，直到可以分成m份数组为止。但显然可以使用二分查找进行优化。
但是用二分查找也有一个不好的地方，就是需要判断二分查找的结束时间，当我们找到一个值ret，确实可以把数组分成m份，还不可以结束二分查找，因为可能max(nums)到ret之间还有值符合要求。所以结束时间应该为无法再去二分的时间点，就是左边界等于右边界。

func splitArray(nums []int, m int) int {
    left, right := 0, 0
    for _, v := range nums {
	right += v
	if left < v {
	    left = v
	}
    }
    for left < right {
        mid := (left + right) / 2
	subSum, cnt := 0, 1
	for _, v := range nums {
	    if subSum+v > mid {
		subSum = v
		cnt++
	    } else {
		subSum += v
	    }
	}
	if cnt > m {
	    left = mid + 1
	} else {
	    right = mid
	}
    }
    return left
}

[yankewei]

JS

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {number}
 */
var splitArray = function(nums, m) {
    let left = 0, right = 0;
    for (let i = 0; i < nums.length; i++) {
        right += nums[i];
        if (left < nums[i]) {
            left = nums[i];
        }
    }
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let subSum = 0, cnt = 1;
        for (let i = 0; i < nums.length; i++) {
            if (subSum + nums[i] > mid) {
                subSum = nums[i];
                cnt++;
            } else {
                subSum += nums[i];
            }
        }
        if (cnt > m) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};