Given an array nums 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.
Example 1:
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.
Example 2:
Input: nums = [1,2,3,4,5], m = 2
Output: 9
Example 3:
Input: nums = [1,4,4], m = 3
Output: 4
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
Solution:
dfs
class Solution {
public int splitArray(int[] nums, int m) {
return dfs(nums, 0, 0, 0, m);
}
private int dfs(int[] nums, int curMax, int currSum, int start, int m) {
if (m == 1) {
int prefixSum = currSum;
for (int i = start; i < nums.length; i ++) {
prefixSum += nums[i];
}
return Math.max(curMax, prefixSum);
}
int n = nums.length;
int res = Integer.MAX_VALUE;
int prefixSum = currSum;
for (int i = start; i <= n - m; i ++) {
prefixSum += nums[i];
res = Math.min(res, dfs(nums, curMax, prefixSum, i + 1, m));
res = Math.min(res, dfs(nums, Math.max(curMax, prefixSum), 0, i + 1, m - 1));
}
return res;
}
}
class Solution {
public int splitArray(int[] nums, int m) {
int right = 0;
for (int val : nums) right += val;
int left = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
int numberOfSubarrays = numberOfSubarrays(nums, mid);
// System.out.println(mid + ", " + numberOfSubarrays);
// too few subarrays, limit is too big
if (numberOfSubarrays <= m) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
private int numberOfSubarrays(int[] nums, int sumLimit) {
int n = nums.length;
int curSum = 0;
int count = 1;
for (int i = 0; i < n; i ++) {
int val = nums[i];
if (val > sumLimit) return n + 1;
if (curSum + val <= sumLimit) {
curSum += val;
} else {
curSum = val;
count ++;
}
}
return count;
}
}