输入是正整数或空整数以及另一个整数K的数组A。

我们应该将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。因此，最大值为7。这不是正确的答案。

哪种算法可以解决此问题？

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