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.
Binary search
def splitArray(self, nums: List[int], m: int) -> int:
def canSplit(maxsum):
ct = 1
cur = nums[0]
for x in nums[1:]:
if x + cur > maxsum:
ct += 1
if ct > m:
return False
cur = x
else:
cur += x
return True
low = max(nums)
high = sum(nums)
res = float('inf')
while low <= high:
mid = low + (high - low) // 2
if canSplit(mid):
res = mid
high = mid - 1
else:
low = mid + 1
return res
dynamic programming or backtracking (high time complexity)
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
n = len(nums)
memo = [[0] * (m + 1) for _ in range(n)]
prefix_sum = [0] + list(itertools.accumulate(nums))
for subarray_count in range(1, m + 1):
for curr_index in range(n):
# Base Case: If there is only one subarray left, then all of the remaining numbers
# must go in the current subarray. So return the sum of the remaining numbers.
if subarray_count == 1:
memo[curr_index][subarray_count] = prefix_sum[n] - prefix_sum[curr_index]
continue
# Otherwise, use the recurrence relation to determine the minimum largest subarray sum
# between curr_index and the end of the array with subarray_count subarrays remaining.
minimum_largest_split_sum = prefix_sum[n]
for i in range(curr_index, n - subarray_count + 1):
# Store the sum of the first subarray.
first_split_sum = prefix_sum[i + 1] - prefix_sum[curr_index]
# Find the maximum subarray sum for the current first split.
largest_split_sum = max(first_split_sum, memo[i + 1][subarray_count - 1])
# Find the minimum among all possible combinations.
minimum_largest_split_sum = min(minimum_largest_split_sum, largest_split_sum)
if first_split_sum >= minimum_largest_split_sum:
break
memo[curr_index][subarray_count] = minimum_largest_split_sum
return memo[0][m]