分割数组的最大值问题
作者：Grey
原文地址：
题目说明#
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
在线测评见：LeetCode 410. Split Array Largest Sum
主要思路#
我们先求整个数组的累加和，假设累加和为 sum，我们可以得到一个结论：
分割的 m 个非空连续子数组，每个数组内元素之和的范围一定在(0,sum]区间内。
如果某种划分下的子数组之和的最大值为 max，则 max 首先肯定在(0,sum]区间内。
所以我们可以尝试将思路转换为：
我们先设置一个 max，子数组的累加和最大值不能超过 max 的情况下，最少可分多少部分？
假设能分 k 个部分，
如果k <= m，说明设置的 max 这种划分是满足条件的，再看 max 是否可以变的更小。
如果k > m，说明设置的 max 这种划分是不满足条件的，需要调大 max 的值。
我们可以通过二分的方式来定位 max 的值。即 max 先取(0,sum]的中点值，得到的划分部分数量为 k， 如果k <= m，则 max 继续去左边取中点位置来得到新的划分 k，
如果k > m，max 继续从右边的中点位置来得到新的划分 k 。
完整代码
class Solution {
public static int splitArray(int[] nums, int m) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int l = 0;
int r = sum;
int ans = 0;
while (l <= r) {
int mid = l + ((r - l) >> 1);
int parts = getParts(nums, mid);
if (parts > m) {
// mid越大，parts才会越小
l = mid + 1;
} else {
ans = mid;
r = mid - 1;
}
}
return ans;
}
// 达到aim要分几部分
public static int getParts(int[] nums, int aim) {
for (int num : nums) {
if (num > aim) {
return Integer.MAX_VALUE;
}
}
int part = 1;
int all = nums[0];
for (int i = 1; i < nums.length; i++) {
if (all + nums[i] > aim) {
part++;
all = nums[i];
} else {
all += nums[i];
}
}
return part;
}
}
其中：int getParts(int[] nums, int aim)方法表示：
在连续子数组之和不超过 aim 的情况下，最少需要几个划分部分。
方法的主要逻辑是：
遍历数组，
如果发现某个元素的值超过了 aim，直接返回系统最大，说明无法得到划分。
如果没有超过 aim，则继续加入下一个元素，直到超过 aim，就定位出一个部分。依次类推，就可以得到最少有几个划分。
由于不回退机制，整个算法时间复杂度 O(N)。
更多地，此题也可以用四边形不等式优化的动态规划来解，但是最优解是二分法。