[leetcode]410-分割数组的最大值
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-array-largest-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
给定一个非负整数数组和一个整数 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，在所有情况中最小。
二、题目解析
咋一看题目，完全不知道如何下手。唯一能想到的一个办法是动态规划，但是动态规划要怎么规划。。。算了，看题解吧。
看了题解才知道要用贪心+二分，所谓贪心，就是一种策略思想，在满足条件的情况下寻找最优解。找最优解的办法就是二分，而实际上也就是不断通过二分遍历和去试。
假设数组为nums，要分成m个子数组。那么不难看出和肯定是在[max(nums), sum(nums)]的范围的：
- 当m等于数组的长度n时，每个元素一个子数组，最大和是数组中的最大元素
max(nums)。 - 当m等于1时，整个数组就是一个子数组，最大和是所有数组的和
sum(nums)。
在了解了这个特性后，就可以使用二分不断遍历范围内的和，然后判断和是不是满足数组条件的和。
判断和是否满足条件的办法：当前遍历到的和是sum，从数组开头开始遍历，计算累加和小于等于sum的子数组总量。如果子数组的数量大于m，说明子数组太多了，也就是sum太小了，把遍历和的左边界设置为sum+1。如果子数组的数量小于或者等于m，说明子数组太少了，sum设置的太大，修改右边界为sum-1。
以测试数据为例，[7,2,5,10,8]的和范围在[10, 32]之间，获取最小的最大和的办法：
第一步，取中值mid=21，计算出来符合条件的子数组为：
[7,2,5,10] [8]子数组m的个数刚好等于2，设置right=mid-1=20，再计算mid=15，符合条件的数组：
[7,2,5] [10] [8]子数组个数为3，大于要求的2，设置left=mid+1=16，计算mid=(16+20)/2=18，符合条件的数组：
[7,2,5] [10,8]子数组个数为2，满足题目要求，设置right=mid-1=17，计算mid=(16+17)/2=16，符合条件的数组：
[7,2,5] [10] [8]子数组个数为3，大于要求的2，设置left=mid+1=17，计算mid=(17+17)/2=17，符合条件的数组：
[7,2,5] [10] [8]子数组个数还是3，大于要求的2，设置left=mid+1=18，此时left大于right(17)，遍历结束，返回18。
三、示例代码
3.1 代码
class Solution {
public:
int splitArray(vector<int> &nums, int m) {
size_t i;
int count = 0;
long left = nums[0], right = 0, mid, sum;
// 确定左边界
for (i = 0; i < nums.size(); i++) {
right += nums[i];
left = left < nums[i] ? nums[i] : left;
}
while (left <= right) {
mid = (left + right) / 2;
sum = 0;
count = 1; // count要初始化为1
// 遍历所有的和
for (i = 0; i < nums.size(); i++) {
// 和超出了，重新计算下一个子数组
if (sum + nums[i] > mid) {
sum = nums[i];
count ++;
} else {
sum += nums[i];
}
}
if (count > m) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (int)left;
}
};
3.2 为什么count初始化为1
在评论区有看到一个问题是问为什么count要初始化为1，回复是说默认情况下是整个数组，所以要加1：
对于这个答案，我是不认可的。
count加1的真正原因是因为最后一个子数组没有计算到count里面去，因为最后一个子数组走不到count++循环就退出了。
cnt=0 cnt=1 循环退出
↓ ↓ ↓
[] [7,2,5] [10, 8]当循环退出的时候count来不及加1就退出了，正确的做法就是在循环结束后再自加一次，初始化为1的目的就是相当于提前加了这个1。
