【Leetcode】410. Split Array Largest Sum 410. 分割数组的最大值
解法
解法一:记忆化搜索+剪枝
每个位置试试,可以加上一个剪枝
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
p = [0]
for a in nums:
p.append(p[-1]+a)
n = len(p)
mem = {}
def solve(j,k):
if k==1:
return p[j]
if (j,k) not in mem:
res = p[j]
for i in xrange(j-1,k-2,-1):
best = max(p[j]-p[i],(p[i]-1)/(k-1)+1)
if best>=res:continue
res = min(res,max(p[j]-p[i],solve(i,k-1)))
mem[(j,k)] = res
return mem[(j,k)]
return solve(n-1,m)
虽然也能过但是巨慢……
解法二:二分搜索
首先对最后的结果的范围进行一个估计
当m为1的时候,结果就是整个数组的和,结果绝对不会超过这个值
当m为整个数组的长度时,结果就是数组里的最大值,结果绝对不会低于这个值
当猜测mid时,假如我们在不超过mid的情况下可劲儿往每个组里塞数,就这样,塞完了组的数量还比m多,那这个mid肯定不行,太小了,要往大了挑
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
l,r = max(nums),sum(nums)
if m==1:
return r
if m==len(nums):
return l
n = len(nums)
def ok(v):
cnt = now = 0
for i in xrange(n):
if now+nums[i]<=v:
now += nums[i]
else:
cnt += 1
now = nums[i]
if now!=0:
cnt += 1
# print cnt
return cnt<=m
while l<r:
mid = (l+r)>>1
# print l,r,mid
if ok(mid):
r = mid
else:
l = mid+1
return r