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;
}