Split Array Largest Sum - LeetCode
Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Example 1: Input: nums = [7,2,5,10,8], m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18. Example 2: Input: nums = [1,2,3,4,5], m = 2 Output: 9
- code #binarySearchAdvanced
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
def isTargetValid(target):
sub_ct = 0
cur_sum = 0
for v in nums:
if v + cur_sum <= target:
cur_sum += v
else:
cur_sum = v
sub_ct += 1
return sub_ct + 1
left, right = max(nums), sum(nums)
res = 0
while left <= right:
mid = left + (right - left) // 2
if isTargetValid(mid) <= m: # need more sub groups, target value should be smaller
res = mid
right = mid - 1
else:
left = mid + 1
return res
- code
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
l, r = max(nums), sum(nums)
ans = r
while l <= r:
mid = l + (r-l) // 2
sub_sum = 0
ct = 1 # not 0
for v in nums:
if sub_sum + v > mid:
sub_sum = v # not 0
ct += 1
else:
sub_sum += v
if ct > m:
l = mid + 1
else:
ans = min(ans, mid)
r = mid - 1
return ans