LC410. Split Array Largest Sum

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

We want to split an array in to m segments, and find the minimum value of the max sum of each segment. We can define ok(s) as whether we can split the array into m segments such that the sum each segment is less than or equal to s. We know when s >= sum(nums), ok(s) = true; when s < max(nums), ok(s) = false. In between, i.e. max(nums) <= s < sum(nums), there is some boundary x such that for s < x, ok(s) = false and for s >= x, ok(s) = true. Therefore, we can treat the ok(s) segment as a sorted array, and use binary search to find our target x.

To evaluate ok(s), we can use a greedy approach by taking as many values as we can for each segment. If we can make every segment sum up to less than or equal to s with less than or equal to m segments, then ok(s) is true.

我们要将一个数组分成 m 段，找到每段和最大值的最小值。我们可以定义 ok(s) 表示是否可以将数组分成 m 段，且每段和都不超过 s。我们知道 s >= sum(nums) 时，ok(s) = true；而 s < max(nums) 时，ok(s) = false。而在中间这一段 max(nums) <= s < sum(nums) 上则是在某个 s 处存在一个分界点 x，当 s < x 时 ok(s) = false，而 s >= x 时 ok(s) = true。因此，我们可以将这一段 ok(s) 看成一段有序数组，使用二分查找来找到我们的目标 x。

判断 ok(s) 时我们可以采用贪心的方法，在每一段中尽可能加入多的数字。如果我们能在 m 段以内做到让每段的和都不超过 s，那么 ok(s) = true

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        return self._binarySearch(nums, m)

    def _binarySearch(self, nums, m):
        l = max(nums)
        r = sum(nums)
        # [x, x, ..., x, v, v, ..., v]
        while l < r:
            print(l, r)
            mid = (l + r) // 2
            if self._ok(nums, mid, m):
                r = mid
            else:
                l = mid + 1
        return l
    
    def _ok(self, nums, maxSum, m):
        curSum = 0
        thisM = 1
        for x in nums:
            if curSum + x <= maxSum:
                curSum += x
            else:
                thisM += 1
                curSum = x
        return thisM <= m