410 Split Array Largest Sum

410. Split Array Largest Sum​
1. Question
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:
Ifnis the length of array, assume the following constraints are satisfied:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50,n)
Examples:
1
Input:
2
​
3
nums = [7,2,5,10,8]
4
​
5
m = 2
6
​
7
Output: 18
8
​
9
Explanation:
10
There are four ways to split nums into two subarrays.
11
The best way is to split it into [7,2,5] and [10,8],
12
where the largest sum among the two subarrays is only 18.
Copied!
2. Implementation
(1) Binary Search
思路：题目的本质是在这数组所有可能的m个subarray的最大sum里找一个最小的，可以利用二分法的思想，找到这个subarrat sum的左边界。做法是找出这个subarray sum的上下限，由于数组的所有元素都是非负的，所以上限就是数组总和，下限就是单独一个元素的最大值(注意，不是最小值，因为是找m个subarray里最大的一个)，在这个范围里做二分
1
class Solution {
2
    public int splitArray(int[] nums, int m) {
3
        int low = Integer.MIN_VALUE, high = 0, mid = 0;
4
​
5
        for (int num : nums) {
6
            low = Math.max(low, num);
7
            high += num;
8
        }
9
​
10
        while (low + 1 < high) {
11
            mid = low + (high - low) / 2;
12
​
13
            if (!isValid(nums, m - 1, mid)) {
14
                low = mid + 1;
15
            }
16
            else {
17
                high = mid;
18
            }
19
        }
20
        return isValid(nums, m - 1, low) ? low : high;
21
    }
22
​
23
    public boolean isValid(int[] nums, int cuts, int target) {
24
        int sum = 0;
25
        for (int num : nums) {
26
            if (num > target) {
27
                return false;
28
            }
29
​
30
            if (sum + num <= target) {
31
                sum += num;
32
            }
33
            else {
34
                --cuts;
35
                sum = num;
36
                if (cuts < 0) {
37
                    return false;
38
                }
39
            }
40
        }
41
        return true;
42
    }
43
}
Copied!
3. Time & Space Complexity
Binary Search: 时间复杂度O(nlog(maxSum - minSum + 1)), n是数组元素个数, 空间复杂度O(1)

374 Guess Number Higher or Lower

436 Find Right Interval

Last modified 2yr ago

Copy link

Contents

410. Split Array Largest Sum

1. Question

2. Implementation

3. Time & Space Complexity

410. Split Array Largest Sum​

1. Question

2. Implementation

3. Time & Space Complexity

410. Split Array Largest Sum