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