【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