题目描述:
LeetCode 410. Split Array Largest Sum
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:
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.
题目大意:
给定一个非负整数数组与一个整数m,你可以将数组拆分成m个非空连续子数组。编写算法使得这m个子数组各自的和的最大值最小化。
注意:
m满足如下约束:1 ≤ m ≤ length(nums) ≤ 14,000
解题思路:
二分枚举答案(Binary Search)
将数组nums拆分成m个子数组,每个子数组的和不小于sum(nums) / m,不大于sum(nums)
又因为数组nums中只包含非负整数,因此可以通过二分法在上下界内枚举答案。
时间复杂度O(n * log m),其中n是数组nums的长度,m为数组nums的和
Python代码:
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
size = len(nums)
high = sum(nums)
low = high / m
while low <= high:
mid = (low + high) / 2
n = m
cnt = 0
valid = True
for x in range(size):
if nums[x] > mid:
valid = False
break
if cnt + nums[x] > mid:
n -= 1
cnt = 0
cnt += nums[x]
if n == 0:
valid = False
break
if valid:
high = mid - 1
else:
low = mid + 1
return low
本文链接:http://bookshadow.com/weblog/2016/10/02/leetcode-split-array-largest-sum/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。