410. Split Array Largest Sum

-
https://leetcode.com/problems/split-array-largest-sum/

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 ≤ 1000
  • 1 ≤ 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.
---
Related problems
---
class Solution {
public int splitArray(int[] nums, int m) {
long lo = 0, hi = 0;
for (int num: nums) {
hi += num;
lo = Math.max(lo, num);
}
long ans = hi;
while (lo <= hi) {
long mid = lo + (hi - lo) / 2;
if (isValid(nums, mid, m)) {
// Save ans and continue searching for new min
ans = Math.min(ans, mid);
// partitions < m => too far out => higher sums => search for lower sums
// search for new minimum largest sum => shrink search space for sums
hi = mid - 1;
} else {
// partitions > m => too close => lower sums => search for higher sums
lo = mid + 1;
}
}
return (int)ans;
}
private boolean isValid(int[] nums, long target, int m) {
long parititions = 1, sum = 0;
for (int num: nums) {
if (sum + num > target) {
sum = num;
parititions++;
} else {
sum += num;
}
}
return parititions <= m;
}
}
view raw 410.SplitArrayLargestSumBinarySearch.java hosted with ❤ by GitHub