题目描述：

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满足如下约束：1 ≤ m ≤ length(nums) ≤ 14,000

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

Pingbacks已关闭。