LeetCode 410. 【Java】410. Split Array Largest Sum
原题链接
困难
作者:
tt2767
,
2020-04-06 16:45:59
,
所有人可见
,
阅读 588
class Solution {
public int splitArray(int[] nums, int m) {
return divide(nums, m);
}
public int divide(int[] nums, int m){
long sum = 0, max = 0;
for (int i = 0; i < nums.length ; i++) {
sum += nums[i];
max = Math.max(max, nums[i]);
}
int result = lowerBound(nums, m, max, sum);
return result;
}
public int lowerBound(int[] nums, int m, long l, long r){
while (l < r){
long mid = l + r >> 1;
if (check(nums, m , mid)) r = mid;
else l = mid + 1;
}
return (int)l;
}
boolean check(int[] nums, int m, long target){
long cur = 0, cnt = 0;
for (int i = 0 ;i < nums.length ; i++){
if (cur + nums[i] <= target) {
cur += nums[i];
} else {
m -- ;
cur = nums[i];
}
}
return m >= 1 ;
}
}