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

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)