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

func splitArray(nums []int, m int) int {
	n := len(nums)
	sum := make([]int, n+1)
	for i := 0; i < n; i++ {
		sum[i+1] += nums[i] + sum[i]
	}
	if m == 1 {
		return sum[n]
	}
	beg, max, target := 0, sum[n]/m, sum[n]/m
	for i := 0; i < m-1; i++ { // Cut m-1 times
		l, r := beg, n
		for l <= r {
			mid := l + (r-l)/2
			if target < sum[mid]-sum[beg] {
				r = mid - 1 // Keep sum[r] - sum[beg] <= target
			} else {
				l = mid + 1
			}
		}
		if val := sum[r] - sum[beg]; val != target && sum[r+1]-sum[beg]-target < target-val {
			r++
		}
		max = maxInt(max, sum[r]-sum[beg])
		beg = r
		target = (sum[n] - sum[beg]) / (m - 1 - i)
		fmt.Println(r)
	}
	fmt.Println(sum, beg, max, target)
	return maxInt(max, sum[n]-sum[beg])
}

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