问题
https://leetcode-cn.com/problems/split-array-largest-sum/
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意: 数组长度 n 满足以下条件:
1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n) 示例:
输入: nums = [7,2,5,10,8] m = 2
输出: 18
解释: 一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
解法
反向查找
如果限定子数组和的大小不高于某值，则一定能得到能分割子数组的数量的最小值。这个最小值若小于题目规定的 m ，则它一定能分成 m 个子数组。
按照前面的思路，只要“某值”最小即可。“某值”的范围一定是 [max(nums), sum(nums)]。
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
42
43
44
def split_array(nums: list, split_count: int):
"""
分割数组，
:param nums:数据
:param split_count:split_count个子数组
:return:
"""
# 元素最大值
max_num = max(nums)
# 元素和
sum_nums = sum(nums)
# 分割数组，子数组的和的最大值范围在左闭右闭的区间 [max_num,sum_nums] 中
for i in range(max_num, sum_nums + 1):
min_count = get_min_split_count(nums, i)
if min_count <= split_count:
# 只要能切割的子数组的数量不大于 m 个即可
return i
return max_num
def get_min_split_count(nums: list, max_sum: int) -> int:
"""
查询按照子数组最大值分割，至少能分多少个子数组
:param nums: 数组
:param max_sum: 子数组最大值
:return: 子数组的数量
"""
count = 1
sum_data = 0
for i in range(len(nums)):
if sum_data + nums[i] > max_sum:
# 如果子数组的和不能再加下一个元素了，结果+1
count += 1
# 重置子数组为当前元素
sum_data = nums[i]
else:
# 既然子数组添加元素仍不超过 max_sum，那就添加
sum_data += nums[i]
return count
if __name__ == '__main__':
l = [7, 2, 5, 10, 8]
print(split_array(l, 2)) # 18
时间复杂度为 \(O(n^2)\)
二分查找改进
上面的时间复杂度过高，高达 \(O(n^2)\)。
for i in range(max_num, sum_nums + 1) 属于线性查找，时间复杂度有 \(O(n)\)。且我们知道遍历的对象是有序的，可以尝试使用二分查找来优化。
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
42
43
44
45
46
47
48
49
50
def split_array(nums: list, split_count: int):
"""
分割数组，
:param nums:数据
:param split_count: split_count个子数组
:return:
"""
# 元素最大值
left = max(nums)
# 元素和
right = sum(nums) + 1
# 分割数组，子数组的和的最大值范围在 [max_num,sum_nums] 中
while left < right:
mid = (left + right) // 2
min_count, sum_data = get_min_split_count(nums, mid)
if min_count > split_count:
# 和小了，能分割的数量过多了，往大缩小范围。
left = mid + 1
else:
# 能分割的数量小于等于要求的，则一定能分割成要求的数量。再往小查找最小的子数组的和。往小缩小范围。
right = mid
# 返回最小的最大值
return left
def get_min_split_count(nums: list, max_sum: int) -> int:
"""
查询按照子数组最大值分割，至少能分多少个子数组
:param nums: 数组
:param max_sum: 子数组最大值
:return: 子数组的数量
"""
count = 1
sum_data = 0
for i in range(len(nums)):
if sum_data + nums[i] > max_sum:
# 如果子数组的和不能再加下一个元素了，结果+1
count += 1
# 重置子数组为当前元素
sum_data = nums[i]
else:
# 既然子数组添加元素仍不超过 max_sum，那就添加
sum_data += nums[i]
return count
if __name__ == '__main__':
l = [7, 2, 5, 10, 8, 12]
print(split_array(l, 2)) # 24
时间复杂度被优化为了 \(O(nlogn)\)。