algorithm - 二维最大子数组

Question

Bentley 的 Programming Pearls(第 2 版)在关于最大子数组问题的章节中描述了它的二维版本:​​

...we are given an n × n array of reals, and we must find the maximum sum contained in any rectangular subarray. What is the complexity of this problem?

Bentley 提到，截至该书出版之日(2000 年)，寻找最佳解决方案的问题尚未解决。
现在还是这样吗？哪个是最著名的解决方案？是否有近期文献的引用资料？

Answer 1

此问题(最大子数组)的一维解决方案是 Theta(n)，使用一种称为“Kadane 算法”的算法(我敢肯定还有其他算法，但我对这个算法有个人经验)。这个问题的二维解决方案(最大子矩形)已知是 O(n^3)，使用 Kadane 算法的实现(我再次确定还有其他算法，但我以前用过这个)。

虽然我们知道可以在 Theta(n^3) 中找到二维解，但是没有人能够证明 n^3 是否是下界。对于许多算法，当您增加一个维度时，您会将算法的下限增加一个恒定的幅度。对于这个特定问题，复杂性不会线性增加，因此没有已知的解决方案适用于任何给定维度，因此问题仍然悬而未决。

引用一个类似的案例:我们知道2个矩阵可以在n^3次内相乘。我相信还有一种算法可以在 n^2.8 中完成。然而，没有数学表明我们不能让它低于 n^2.8，所以它仍然是一个“开放”算法。