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:
Ifnis 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.
class Solution {
public int splitArray(int[] nums, int m) {
int low = Integer.MIN_VALUE, high = 0, mid = 0;
for (int num : nums) {
low = Math.max(low, num);
high += num;
}
while (low + 1 < high) {
mid = low + (high - low) / 2;
if (!isValid(nums, m - 1, mid)) {
low = mid + 1;
}
else {
high = mid;
}
}
return isValid(nums, m - 1, low) ? low : high;
}
public boolean isValid(int[] nums, int cuts, int target) {
int sum = 0;
for (int num : nums) {
if (num > target) {
return false;
}
if (sum + num <= target) {
sum += num;
}
else {
--cuts;
sum = num;
if (cuts < 0) {
return false;
}
}
}
return true;
}
}
class Solution {
public int splitArray(int[] nums, int m) {
int n = nums.length;
int[] sum = new int[n + 1];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = i - 1; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][k], sum[j] - sum[k]));
}
}
}
return dp[m][n];
}
}