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:
Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

Examples:

1
2
3
4
5
6
7
8
9
10
11
Input:
nums = [1,2,3,4,5]
m = 2
Output:
9
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5],
where the largest sum among the two subarrays is only 9.

方法1: 暴力穷举每一种分法(回溯法),第一个想到的就是这种做法
方法2:Binary Search
Ref: https://discuss.leetcode.com/topic/61315/java-easy-binary-search-solution-8ms
刚开始想的时候有点感觉,但是还是没能自己写出来。
其实就是尽量把一个数据尽量平均的分成m份。譬如说示例中的[1,2,3,4,5], 分成两份,可以分成(1, 14), (3, 12), (6, 9), (10, 5), 其中(6, 9)最平均,所以结果是9. 这是一种正向的思维方式。
倒过来说,如果我给定一个值target, 看一个数组中能不能至少分成m个正好<=sum的数组,如果可以,说明target小了,如果不可以,说明target大了。正好符合Binary Search的思想。

代码如下:
代码跟引用中给的代码略不同,应用了九章的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
33
34
35
36
37
38
39
40
41
public int splitArray(int[] nums, int m) {
long sum = 0;
int max = 0;
for (int num : nums) {
max = Math.max(max, num);
sum += num;
}
return (int) binary(nums, m, sum, max);
}
private long binary(int[] nums, int m, long high, long low) {
long mid = 0;
while (low + 1 < high) {
mid = low + (high - low) / 2;
if (valid(nums, m, mid)) {
low = mid;
} else {
high = mid;
}
}
if (valid(nums, m, high))
return high;
return low;
}
private boolean valid(int[] nums, int m, long target) {
int sum = 0;
int count = 0;
for (int num : nums) {
sum += num;
if (sum >= target) {
sum = num;
count++;
if (count == m) {
return true;
}
}
}
return false;
}