410. 分割数组的最大值

题目

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组，使得这 k 个子数组各自和的最大值 最小。

返回分割后最小的和的最大值。

子数组 是数组中连续的部份。

解法

int splitArray(vector<int>& nums, int m) {long l = nums[0], h = 0;//int类型在这里不合适，因为h可能会超过int类型能表示的最大值for (auto i : nums){h += i;l = l > i ? l : i;}while (l<h){long mid = (l + h) / 2;long temp = 0;int cnt = 1;//初始值必须为1for(auto i:nums){temp += i;if(temp>mid){temp = i;++cnt;}}if(cnt>m)l = mid + 1;elseh = mid;}return l;}

不仅可以查找数组索引，还可以查找和的范围，这就是需要到sum里面去查找，只要这个数在这个范围内，就一定能够查找到。