这是一道二分题，主要的特点在于提到了“最大值最小”

基本思路是先不考虑分段次数，从最小的和枚举到最大的和，看哪个和满足指定分段次数m相等

最小的和：全部都分段，此时最小和为max(arr)

最大的和：只分一段，此时最大和为sum(arr)

其实可以在最小和和最大和直接直接遍历，但是为了加速，使用二分查找

对于left mid right分段的左右区间，有三种情况，若

分段数 > 指定分段次数 ， 说明指定的和太小，应该让和大点，才能让分段次数少点，因此进入右区间left = mid + 1

分段数 = 指定分段次数 ， 此时分段数刚刚好，若是从小到大遍历，可直接退出， 但是倘若是二分查找，得继续往左区间看有没有更小的分段次数满足要求，因此right = mid -1

分段数 < 指定分段次数 ， 说明此时指定的和太大，导致分段数太少，因此要让和小一点，因此进入左区间，right = mid -1

综合三种情况就有

当 分段数>指定分段次数，进入右区间

当 分段数<=指定分段次数，进入左区间

以下为代码

其中，check函数的作用在于给定一个和MaxSum，在数组arr中找到根据该给定和可以分成多少组，最后将最后分得组数和指定组数m做对比，然后指导下一步操作。

def check(maxSum, arr, m):
	# cnt初始化为1是因为若直接进入循环，cnt实际上漏算了最后一个分组
	Sum, cnt = 0,1
	for num in arr:
		if Sum + num <= maxSum:
			Sum += num
		else:
			Sum = num
			cnt += 1
	return cnt > m

if __name__ == '__main__':
	n, m = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	left = max(arr)
	right = sum(arr)
	# 从最大值和全部值的和做二分
	while left <= right:
		mid = (left + right) // 2
		if check(mid, arr, m):
			left = mid + 1
		else:
			right = mid - 1
	print(left)