在O（n^2）中寻找一个最大可能总和的子矩阵

我试图用Java编写一个程序，当给出一个MxN矩阵时，它会找到数目最大的（连续的）子矩阵。程序然后需要返回子矩阵的左上角坐标和右下角坐标。矩阵可以包含负数，矩阵和子矩阵不需要是正方形的。在O（n^2）中寻找一个最大可能总和的子矩阵

我看到这是在这里讨论：Getting the submatrix with maximum sum?和解决方案似乎是O（n^3）。我的一位朋友说他们曾经设法解决O（n^2）中的这个问题。还建议here.这可能吗？

是否有任何可用的代码，以最有效的方式解决这个问题？

2010-06-25 Meir

第二SO问你链接到同为O（n^2）解决方案，讨论了比你更简单的问题。 – stephan 2010-06-25 07:20:42

你（很可能）无法解决你的问题O(n^2)，至少没有这样的算法是已知的。最佳解决方案具有亚立方复杂性，但实施起来非常困难，实践中可能较慢。你可以阅读一篇关于它的文章here。

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

2010-06-25 07:04:29 IVlad

这篇论文的链接不起作用 – user674669 2012-10-20 10:32:02

@IVIad你是说如果我找到一个二次方案，我可以发表一篇论文吗？ – dhruvbird 2016-10-26 19:57:34

（S）他是你的朋友..所以只是问他/她，做与我们分享太:)

2010-06-25 09:48:08 GadaaDhaariAvi

回答