leetcode 410 Split Array Largest Sum
z
 2019-04-14 19:42:37  

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 msubarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

Examples:

1
2
3
4
5
6
7
8
9
10
11
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.
  • 最小的返回值是，当m为len(nums)的时候，max(nums)就是返回值。
  • 最大的返回值是，当m为1的时候，sum(nums)就是返回值。
  • 因此，我们可以在max(nums)和sum(nums)这个区间找到minimize largest sum
    • 采用二分查找的方法，取中位数mid。判断中位数是否能够成为每一个split的larget sum
    • 遍历nums数组，贪心的进行分组。如果累加到当前位置的和大于mid，就进行一个新的划分。并统计当前的划分个数。
    • 如果划分个数已经大于m。说明还有多的数。那么minimize largest sum应该大于mid，这样，left = mid+1。
    • 否则，就说明当前的数都已经有了划分，并且要么划分个数没有到达m个，或者刚好等于m个。
      • 如果是没有到达m个，就需要从其他的划分中取出数组成新的split，这样一来，当前的minimize largest sum 要进一步减小，right = mid
        • 如果已经到达了m个，第m个split中的sum可能这m个split的每一个sum都小于mid, 当前的minimize largest sum 要进一步缉拿小，right = mid
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
class Solution {
    public int splitArray(int[] nums, int m) {
        int max = 0;
        long sum = 0;
        for (int i: nums) {
            max = Math.max(max, i);
            sum += i;
        }
        long l = max;
        long r = sum;
        
        if (m == 1) return (int) sum;
        
        while (l < r) {
            long mid = l + (r - l)/2;
            if (isLeft(nums, mid, m)) {
                l = mid + 1;
            }
            else 
                r = mid;
        }
        return (int) l;
    }
    
    public boolean isLeft(int[] nums, long target, int m) {
        int split = 1;
        long sum = 0;
        for (int i: nums) {
            sum += i;
            if (sum > target) {
                sum = i;
                split ++;
                if (split > m) {
                    return true;
                }
            }
        }
        return false;
    }
}