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.思路：这种求最大值最小化的问题，就是BS的讨论，对最后可能的结果直接进行二分，然后判断是否可以到达mid，如此而已
public class Solution { public int splitArray(int[] nums, int m) { int max = Integer.MIN_VALUE, sum = 0; for(int i : nums) { sum += i; max = Math.max(max, i); } // BS int lo = max, hi = sum; while(lo <= hi) { int mid = lo + (hi - lo) / 2; if(canGet(nums, mid, m)) lo = mid + 1; else hi = mid - 1; } return lo; } private boolean canGet(int[] nums, int mid, int m) { int cnt = 0, sum = 0; for(int i=0; i<nums.length; i++) { if(sum + nums[i] > mid) { cnt ++; if(cnt == m) return true; sum = nums[i]; continue; } sum += nums[i]; } return false; } }
