LeetCode: Split Array Largest Sum

Posted on June 18, 2019July 26, 2020 by braindenny

Split Array Largest Sum

Similar Problems:

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:
If n is the length of array, assume the following constraints are satisfied:

1 <= n <= 1000
1 <= m <= min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

## https://code.dennyzhang.com/split-array-largest-sum
## Basic Ideas: dynamic programming
##
##   dp(i, j)
##     nums[:i]
##     j
##            nums[i] is the last element
##            nums[k:i]
##              min(max(dp(k-1, j-1), sums[k:i]))
##
## Complexity: Time O(n*n*m), Space O(n*m)
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        dp = [[sys.maxsize for _ in range(m+1)] for _ in range(n+1)]
        sums = [0]*(n+1)
        for i in range(n):
            sums[i+1] = sums[i] + nums[i]

        dp[0][0] = 0
        for i in range(1, n+1):
            for j in range(1, m+1):
                # nums[:i]
                for k in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[k][j-1], sums[i]-sums[k]))
        return dp[-1][-1]

## https://code.dennyzhang.com/split-array-largest-sum
## Basic Ideas: binary search + greedy
##
##    The value is integer. It's in the range of [maxVal, sumVal]
##   
## Complexity: Time O(n*log(sum_n)), Space O(n)
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def canDivide(nums, mid, m):
            curSum = 0
            for i in range(len(nums)):
                curSum += nums[i]
                if curSum > mid:
                    curSum = nums[i]
                    m -= 1
            if curSum >0: m -= 1
            return m>=0

        left, right = max(nums), sum(nums)
        while left<right:
            mid = left+int((right-left)/2)
            if canDivide(nums, mid, m):
                # F, F, F, T, T, T
                right = mid
            else:
                left = mid+1
        return left

Post Views: 0