05 August 2008
给定一个由非负整数和一个整数 m 组成的数组 nums，您可以将数组拆分为 m 个非空连续子数组。
编写一个算法来最小化这 m 个子数组中的最大和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private static boolean feasible(int[] nums, int mid, int m) {
int mDone = 1;
int idx = 0;
int sumSoFar = 0;
while (idx < nums.length) {
sumSoFar += nums[idx];
if (sumSoFar > mid) {
mDone++;
sumSoFar = nums[idx];
if (mDone > m) {
return false;
}
}
idx++;
}
return true;
}
public int splitArray(int[] nums, int m) {
int left = Arrays.stream(nums).max().getAsInt(), right = Arrays.stream(nums).sum();
while (left < right) {
int mid = left + (right - left) / 2;
if (feasible(nums, mid, m)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
DP
dp[s,j] is the solution for splitting subarray n[j]…n[L-1] into s parts.
dp[s+1,i] = min{ max(dp[s,j], n[i]+…+n[j-1]) }, i+1 <= j <= L-s
ptifalls:
1, init when s== 1; start loop when s = 2;
2, for each s, loop i until n - 1 - (s - 1) to make sure the rest will form s - 1 parts;
3, same on j, until n - 1 - (s - 2) to make sure the rest will form s - 2 parts;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int splitArray(int[] nums, int m) {
int len = nums.length;
int[] sum = new int[len + 1];
sum[0] = 0;
for (int i = 0; i < len; i++) {
sum[i + 1] = sum[i] + nums[i];
}
int[][] dp = new int[m + 1][len];
for (int i = 0; i < len; i++) {
dp[1][i] = sum[len] - sum[i];
}
for (int s = 1; s < m; s++) {
for (int i = 0; i < len - s; i++) {
dp[s + 1][i] = Integer.MAX_VALUE;
for (int j = i + 1; j <= len - s; j++) {
int t = Math.max(dp[s][j], sum[j] - sum[i]);
if (t <= dp[s + 1][i]) {
dp[s + 1][i] = t;
} else break;
}
}
}
return dp[m][0];
}
}