LeetCode: 410. Split Array Largest Sum

DP Solution

Time complexity: O(M*N**2)

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        self.nums = nums
        self.table = [0] * (len(nums)+1)
        summed = 0
        for i in range(len(nums)):
            summed += nums[i]
            self.table[i+1] = summed
        self.dp = {}
        return self.helper(0, len(nums)-1, m)
        
    def helper(self, i, j, m):
        if m == 1:
            return self.table[j+1] - self.table[i]
        if i == j:
            return self.nums[i]
        
        if (i, j, m) in self.dp:
            return self.dp[(i, j, m)]
        
        ret = int(1e9)
        for k in range(i, j-m+2):
            ret = min(ret, max(self.table[k+1]-self.table[i],
                               self.helper(k+1, j, m-1)))
        self.dp[(i, j, m)] = ret
        return ret

 

Binary Search Solution

Perhaps this is the most efficient solution. I guess the most difficult part of this solution is 'coming up with binary search'.

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def num_bins(val):
            cnt = 0
            summed, maxsum = 0, 0
            for num in nums:
                summed += num
                if summed > val:
                    summed = num
                    cnt += 1
                maxsum = max(maxsum, summed)
            maxsum = max(maxsum, summed)
            return cnt + 1, maxsum
        
        ret = sum(nums)
        left, right = max(nums), sum(nums)
        while left <= right:
            mid = (left + right) // 2
            k, maxsum = num_bins(mid)
            if k <= m:
                ret = min(ret, mid)
                right = mid - 1
            else:
                left = mid + 1
        return ret