410. Split Array Largest Sum

LeetCode 410. Split Array Largest Sum

Description

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

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 10^6

• 1 <= m <= min(50, nums.length)

Tags

Binary Search, Dynamic Programming

Solution

Totally same as LeetCode 1011. See Reference.

Complexity

• Time complexity: $O(n\log(\Sigma nums))$

• Space complexity: $O(1)$

Code

func splitArray(nums []int, m int) int {
	var l, r int
	for _, num := range nums {
		if num > l {
			l = num
		}
		r += num
	}
	for l < r {
		mid := l + (r-l)/2
		if subsRequired(nums, mid) > m {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

func subsRequired(nums []int, cap int) int {
	subs, C := 1, cap // 1 for the last subarray
	for _, num := range nums {
		if num > cap {
			subs++
			cap = C - num
		} else {
			cap -= num
		}
	}
	return subs
}

Reference

1. 1011. Capacity To Ship Packages Within D Days

2. 分割数组的最大值