在O(n^2)时间复杂度下寻找具有最大可能总和的子矩阵

Question

3

我正在尝试用Java编写一个程序，当给定一个MxN矩阵时，它将找到数字和最大的（连续的）子矩阵。然后程序需要返回子矩阵的左上角坐标和右下角坐标。矩阵可以包含负数，且矩阵和子矩阵都不需要是正方形。

我看到这个问题在这里已经被讨论过：Getting the submatrix with maximum sum?，那里的解决方案似乎是O(n^3)。我的朋友说他们曾经成功地用O(n^2)解决了这个问题。也可以在这里找到相关信息。这种问题有没有最有效的可用代码呢？

- Meir

你链接的第二个SO问题中提供的O(n^2)解决方案讨论的是一个比你的问题更简单的问题。 - stephan

2个回答

4

他/她是你的朋友，所以只需问他/她，然后与我们分享即可 :)

- AviD

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

你（很可能）无法用O(n^2)的算法解决问题，至少目前没有已知的这样的算法。最优解的复杂度低于立方级别，但实现起来非常困难，而且在实践中可能会更慢。你可以在这里阅读相关论文。

通常使用的算法是在你找到的问题中引用的O(n^3)算法。