leetcode-go/leetcode/hard/410.split-array-largest-sum.go

func splitArray(nums []int, m int) int {
	if len(nums) == 0 {
		return 0
	}
	l, r := nums[0], 0 // max, sum
	for _, i := range nums {
		l = maxInt(l, i)
		r += i
	}
	for l <= r {
		mid := l + (r-l)/2
		if isValid(nums, m, mid) { // res <= mid, mid is big enough
			r = mid - 1
		} else { // mid < res
			l = mid + 1
		}
	}
	return l
}

func isValid(nums []int, m, max int) bool {
	cnt, sum := 1, 0
	for _, i := range nums {
		if max < sum+i {
			sum = i
			cnt++
			if m < cnt {
				return false
			}
		} else {
			sum += i
		}
	}
	return true
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}