[每日一题]410. Split Array Largest Sum

今天的题目的难度是Hard，写起来有点吃力，理解起来也很吃力。算是一次不小的锻炼吧。题目描述如下稍微解释一下...



今天的题目的难度是Hard，写起来有点吃力，理解起来也很吃力。算是一次不小的锻炼吧。题目描述如下



稍微解释一下，因为题目理解起来比较绕。

给定一个正整数数组nums, 将其分成m个子数组（子数组至少应该有一个元素），那么每一次分的子数组中的元素求和，会有一个最大值，建设是sum。

问题是求所有的分法中，sum最小的值是多少。

题目中举了一个例子。

给定

nums = [7,2,5,10,8]
m = 2那么有如下几种分法:

第一种分法
[7], [2,5,10,8] 最大和是 2 + 5 + 10 + 8 = 25

第二种分法
[7,2], [5,10,8] 最大和是 5 + 10 + 8 = 23

第三种分法
[7,2,5], [10, 8] 最大和是 10 + 8 = 18

第四种分法
[7, 2, 5, 10], [8] 最大和是 7 + 2 + 5 + 10 = 24
结果比较发现， 第三种分法的结果是最小的。所有结果是 18

思路解析：



如下我给出二分法的第一版本



错误解析

这个版本Timeout，原因是我的区间取值范围错误。上面的代码，我的取值范围是 [ nums[0], sum(nums) ] (解释： nums[0] 数组的第一个元素， sum(nums) 数组之和)。所以，遇到一些特别的case, 比如 [1, 238233233233], m = 2这种，就会Timeout 。实际上， 我们要求的值不可能比数组中的最大的数小，所以区间是可以进一步缩小的。 如下是修改后的代码，AC了。





代码解释

在主函数split_array中， 我取数组最大值和数组之和作为取值区间。然后是二分法的标准套路，除了要注意，我取的是闭区间，没有什么可说的。主要是guess函数。

guess 函数接受三个参数：

1. mid: 我们猜测的值
2. nums: 原数组
3. m: 子数组个数（nums应该分成m个连续子数组）

guess方法的逻辑就是在已知最大和(mid)的情况下，计算nums可以分成多少个子数组。具体的逻辑可以举个例子说明

nums = [7,2,5,10,8]
m = 2mid = 10上面的参数，假设是我们传递到guess方法中的。那么在最大和为10 的情况下，nums会分成如下4个部分

[7,2], [5], [10], [8]因为m < 4, 所以我们猜测的mid应该比实际的答案小（原因见分析部分）。所以区间应该向右移。

@TK 提供的解题思路



他的代码如下



总结

1. 二分法的前置条件是求的结果必须跟一个变量是单调递增或者递减的关系
2. 二分法的区间应该尽量的小，否则遇到特别的case就会超时
3. 二分法的开闭区间的移动条件是不一样的，写代码的时候一定要注意

“每日一题”群是一个一起刷leetcode的群。我们每天早上会发一道算法题，每天晚上一起讨论解法和套路。通过讨论和分析，一起寻找解决方案，一起提高算法水平。欢迎能坚持每天刷题的朋友加入！

想加群的朋友请加我的微信: fw_xhde

    关注 一个技术人员的胡言乱语