410. Split Array Largest Sum

Problem

Given an array 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.

Note:If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

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.

Problem Summary

Given a non-negative integer array and an integer m, you need to split this array into m non-empty continuous subarrays. Design an algorithm to minimize the largest sum among these m subarrays.

Note: The array length n satisfies the following constraints:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Solution Approach

• Given an array and the number of splits M. The requirement is to split the array into M subarrays and output the maximum subarray sum.
• This problem can be solved with dynamic programming (DP), or with binary search. This is a max-min problem in binary search. The problem can be transformed into finding an x among the M partitions such that x satisfies: for any S(i), S(i) ≤ x holds. This condition guarantees that x is the maximum among all S(i). What is required is the smallest x that satisfies this condition. The search range of x is [max, sum]. Gradually use binary search to approach the low value until finding the smallest low that satisfies the condition, which is the final answer.

Code

package leetcode

func splitArray(nums []int, m int) int {
	maxNum, sum := 0, 0
	for _, num := range nums {
		sum += num
		if num > maxNum {
			maxNum = num
		}
	}
	if m == 1 {
		return sum
	}
	low, high := maxNum, sum
	for low < high {
		mid := low + (high-low)>>1
		if calSum(mid, m, nums) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func calSum(mid, m int, nums []int) bool {
	sum, count := 0, 0
	for _, v := range nums {
		sum += v
		if sum > mid {
			sum = v
			count++
			// Split into m blocks; only m - 1 dividers are needed
			if count > m-1 {
				return false
			}
		}
	}
	return true
}