Problem statement

https://leetcode.com/problems/split-array-largest-sum/

Solution 1

One way is to use binary search for Q: check if we can split numbers into m groups such that the largest sum $\leqslant Q$. We do it in greedy way.

Complexity

Time complexity of this approach is O(n * log(SUM)), where SUM is sum of all numbers in array. Space complexity is O(1).

Code

class Solution:
    def splitArray(self, nums, m):
        def check(Q):
            if max(nums) > Q: return False
            acc, ans = 0, 1
            for num in nums:
                if acc + num <= Q:
                    acc += num
                else:
                    acc = num
                    ans += 1
            return ans <= m
        
        beg, end = max(nums) - 1, sum(nums)
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid):
                end = mid
            else:
                beg = mid
        
        return end

Solution 2

Another solution is use DP: let dp[i][j] be an answer for first i numbers and j groups. Then to evaluate dp[i][j] we need to look find $\min\limits_k$[max(dp[k][j-1], S_k-S_i)], where $S_k$ are cumulative sums. To find this minimum we can either use linear search with $O(m n^2)$, but it will give TLE. Alternative is to use binary search, where we use the property that first term of max is increasing and the second is decreasing.

Complexity

Time complexity is $O(mn\log n)$, space is $O(n)$.

Code

class Solution:
    def splitArray(self, nums, m):
        n = len(nums)
        acc = [0] + list(accumulate(nums))
        dp = list(acc)
        
        for j in range(1, m):
            for i in range(n, j, -1):
                beg, end = j - 1, i
                while beg + 1 < end:
                    mid = (beg + end)//2
                    if dp[mid] >= acc[i] - acc[mid]:
                        end = mid
                    else:
                        beg = mid
                    dp[i] = min(max(dp[end], acc[i] - acc[end]), max(dp[beg], acc[i] - acc[beg]))
        
        return dp[-1]