本文主要是介绍20-二分-值域二分-分割数组的最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是二分法的第20篇算法，力扣链接。
给定一个非负整数数组
nums和一个整数k，你需要将这个数组分成k个非空的连续子数组。设计一个算法使得这
k个子数组各自和的最大值最小。示例 1：
输入：nums = [7,2,5,10,8], k = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。示例 2：
输入：nums = [1,2,3,4,5], k = 2 输出：9
这道题先不暴力了，暴力一点都不好玩，我们可以试试二分法解决问题。
使得..最大值最小是标准二分法的套路，背下来，要考的。
但是二分法要求得是个有序的序列啊，这个什么是有序的呢，和是有序的。我们可以让右边界为整个数组的和，左指针为数组的最小值。
那左右移动的临界条件怎么判断呢？我们可以利用贪心的逻辑去判断。
设已经累加的值为sum，切的刀为cnt，每当sum + num > mid 的时候就去追加一刀重新开始，当刀数不够就左指针右移，刀数正好或者富裕就右指针左移。
func splitArray(nums []int, k int) int {l, r := 0, 0for _, num := range nums {r += numif l < num {l = num}}for l <= r {mid := l + (r-l)/2if checkCount(nums, mid, k) {r = mid - 1} else {l = mid + 1}}return l
}func checkCount(nums []int, mid int, k int) bool {sum, cnt := 0, 1for _, num := range nums {if sum+num > mid {cnt++sum = num} else {sum += num}}return cnt <= k
}
当然，这道题也适合动态规划，在后续动态规划的篇章再来重温。
这篇关于20-二分-值域二分-分割数组的最大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
