# 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
```