如何以最小化每个分区总数的最大值的方式对整数数组进行分区？

Question

输入是一个正整数或空整数的数组A和另一个整数K.我们应该把A划分为K个连续元素的块（用“分区”表示A的每个元素都属于某个块，2不同的块不包含任何共同的元素）。

我们将块的总和定义为块的元素总和。

目标是在K块中找到这样一个分区，使得每个块的最大总和（我们称之为“MaxSumBlock”）被最小化。

我们需要输出MaxSumBlock（我们并不需要找一个实际的分区）

下面是一个例子：

输入：

A = {2, 1, 5, 1, 2, 2, 2} 
K = 3 

预期输出：

MaxSumBlock: 6 
(with partition: {2, 1}, {5, 1}, {2, 2, 2}) 

在预期输出中，每个块的总和为3,6和6.最大值为6.

下面是一个非最佳划分：

partition: {2, 1}, {5}, {1, 2, 2, 2} 

在这种情况下，每个块的总和是3，6和7 max是7，因此它不是一个正确的答案。

什么算法可以解决这个问题？

编辑：K和A的大小不大于100'000。 A的每个元素不大于10'000

Answer 1

使用二分查找。

设最大和范围从0到sum（数组）。所以，mid =（范围/ 2）。通过在O（n）时间内划分为k集来查看mid是否可以实现。如果是，则进入较低范围，否则进入较高范围。

这会给你O（n log n）的结果。 PS：如果您在编写代码时遇到任何问题，我可以帮忙，但我建议您先尝试一下。

编辑：
的要求，我将解释如何找到，如果mid可以划分为O（n）的时间来实现到k套。
遍历元素直到总和小于或等于mid。一旦它大于mid，让它成为下一组的一部分。如果获得k或更少组，则mid可以实现，否则不可以。