Split Array Largest Sum

Problem Id: 410 Difficulty: Hard


Intuition

Solution


class Solution:
    @staticmethod
    def _possible_split(nums, m, limit):
        count = 0
        tmp = 0
        for num in nums:
            if tmp + num > limit:
                tmp = 0
                count += 1
                if count > m:
                    return False
            tmp += num
        if tmp:
            count += 1
        return count <= m

    def splitArray(self, nums: List[int], m: int) -> int:
        hi = sum(nums)
        lo = max(nums) - 1
        while hi - lo > 1:
            mid = (hi + lo) // 2
            if self._possible_split(nums, m, mid):
                hi = mid
            else:
                lo = mid
        return hi