Problem
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Note:If n is the length of array, assume the following constraints are satisfied:
1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)Examples:
Input:nums = [7,2,5,10,8]m = 2
Output:18
Explanation:There are four ways to split nums into two subarrays.The best way is to split it into [7,2,5] and [10,8],where the largest sum among the two subarrays is only 18.
Solution
class Solution {
public int splitArray(int[] nums, int m) {
long sum = 0L, max = 0L;
for (int num: nums) {
sum += (long) num;
max = (long) Math.max(max, num);
}
if (m == 1) return (int) sum;
long l = max, r = sum;
while (l <= r) {
long mid = l + (r-l)/2;
if (valid(nums, mid, m)) r = mid-1;
else l = mid+1;
}
return (int) l;
}
private boolean valid(int[] nums, long target, int m) {
int count = 1;
long sum = 0L;
for (int num: nums) {
sum += num;
if (sum > target) {
count++;
sum = num;
if (count > m) return false;
}
}
return true;
}
}