做了Zenefits的OA，比面经里的简单多了。。害我担心好久
阴险的Baidu啊，完全没想到用二分，一开始感觉要用DP，类似于极小极大值的做法。
然后看了答案也写了他妈好久。
思路是再不看M的情况下，最终结果的取值范围是[最大的元素，所有元素之和]，然后就是用二分在这个范围里找。
注意二分的取舍要配合取舍方程，我用的方程是，保证子集的和都小于等于二分测试的那个二分M，然后集合数小于要求的m。一旦子集数量超过m，说明我们测试的二分M太小了，弄大点，才能让每个子集多放点元素，从而使得总子集数不超过m.
所以返还失败的情况下 L = M + 1
返还成功并不代表就是解，它仅仅表示当前二分M可以使得分出的子集数不超过m，所以R=M作为候选，这样最后判断失败保留的R就是最后一次成功的判断。
反正我这里写了好久，一开始套用yes right, no left的二分判断，判断之后还要重新遍历一次，看看最后的值是否是正确的解，是的话返还R，不是的话返还R+1.
最后，数组里还混杂了Integer.MAX_VALUE，所以计算的时候得改成LONG才行。
主要是卡二分，80%的时间卡在二分上。。越做题越发现自己不会二分了。
ref: leetcode discuss board
(https://discuss.leetcode.com/topic/61315/java-easy-binary-search-solution-8ms)
public class Solution
{
public int splitArray(int[] nums, int m)
{
long max = 0; // largest sum
long maxVal = -1; // smallest sum
//Arrays.sort(nums);
for(int i = 0; i < nums.length;i++)
{
max += nums[i];
maxVal = Math.max(maxVal,nums[i]);
}
if(m == 1) return (int)max;
long res = search(nums,m,max,maxVal);
return (int)res;
}
public long search(int[] nums, int m, long max, long maxVal)
{
long L = maxVal;
long R = max;
while(L < R)
{
long M = L + (R - L)/2;
if(isOK(M,nums,m))
{
R = M;
}
else
{
L = M + 1;
}
}
return R;
}
public boolean isOK(long M, int[] nums, int m)
{
int num = 1;
long cur = 0;
for(int i = 0; i < nums.length;i++)
{
if(cur + nums[i] <= M)
{
cur += nums[i];
}
else
{
num++;
cur = nums[i];
if(num > m) return false;
}
}
return true;
}
/*
[1,2,3,4,5]
2
[1,2,3,4,5,5,6,7,8,9,10,13,15,16,17,18,23,25,46,58]
3
[1,2147483646]
1
*/
}
求Zenefits给个机会吧。。给你跪舔了。