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.
代码
Approach #1 Dynamic Programming
Let's define f[i][j] to be the minimum largest subarray sum for splitting nums[0..i] into j parts.
Time: O(N^2 M) && Space: O(NM)
class Solution {
public int splitArray(int[] nums, int m) {
int n = nums.length;
int[][] f = new int[n + 1][m + 1];
int[] sub = new int[n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < n; i++) {
sub[i + 1] = sub[i] + nums[i];
}
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < i; k++) {
f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
}
}
}
return f[n][m];
}
}
Approach #2 Binary Search + Greedy
Set the search range between min=(largest single value) and max=(sum of all values).
The min starts there because we're looking for the sum of the largest group in the final set of groups. And no matter what groups you create, the largest value has to be in it, so the largest group can't be smaller than that. (This assumes no negative numbers.)
class Solution {
public int splitArray(int[] nums, int m) {
long l = 0;
long r = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
r += nums[i];
if (l < nums[i]) {
l = nums[i];
}
}
long ans = r;
while (l <= r) {
long mid = (l + r) >> 1;
long sum = 0;
int cnt = 1;
for (int i = 0; i < n; i++) {
if (sum + nums[i] > mid) {
cnt++;
sum = nums[i];
} else {
sum += nums[i];
}
}
if (cnt <= m) {
ans = Math.min(ans, mid);
r = mid - 1;
} else {
l = mid + 1;
}
}
return (int)ans;
}
}
Approach #0 Brute Force
Time complexity : O(n^m)
Space complexity : O(n)
class Solution {
private int ans;
private int n, m;
private void dfs(int[] nums, int i, int cntSubarrays, int curSum, int curMax) {
if (i == n && cntSubarrays == m) {
ans = Math.min(ans, curMax);
return;
}
if (i == n) {
return;
}
if (i > 0) {
dfs(nums, i + 1, cntSubarrays, curSum + nums[i], Math.max(curMax, curSum + nums[i]));
}
if (cntSubarrays < m) {
dfs(nums, i + 1, cntSubarrays + 1, nums[i], Math.max(curMax, nums[i]));
}
}
public int splitArray(int[] nums, int M) {
ans = Integer.MAX_VALUE;
n = nums.length;
m = M;
dfs(nums, 0, 0, 0, 0);
return ans;
}
}