最小最大邻接k划分的快速算法

Question

我正在阅读这个http://www.cas.mcmaster.ca/~terlaky/4-6TD3/slides/DP/DP.pdf，并想知道是否存在一个解决分区问题时间复杂度更高的解决方案。

从链接中：

假设给定的非负数排列S {s1，.，sn}和整数k。如何将S切成k或更小的范围，从而使所有范围内的最大和最小？

例如：

S=1，2，3，4，5，6，7，8 9 k=3 通过将S切成这三个区间，最大范围之和(8,9)为17，这是可能的最小值。 1，2，3，4，5-6，7-8，9

链接中提出的算法在O(kn^2)中运行，并使用O(kn)空间。有没有更有效的算法？

Answer 1

好吧，很显然这是因为“离题”而关闭的！？但是现在它又恢复了，所以无论如何，我找到了一个二进制搜索答案的解决方案。对不起，我忘记了其中一个约束，即所有整数的和不会超过2^64。所以让C=所有整数的累积和。然后，我们可以使用

bool isPossible(int x)

如果可以将S划分为最大分区和小于X的k个分区，则返回true函数。isPossible(int )可以在O(n)中完成(从左到右添加所有内容，如果它超过x，则创建一个新分区)。因此，总的运行时间是O(n*log)。