3

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

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

有没有可用的代码以最有效的方式解决这个问题？

4

2 回答 2

7

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

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

于 2010-06-25T07:04:29.087 回答
4

(S)他是你的朋友..所以问问他/她，也和我们分享:)

于 2010-06-25T09:48:08.190 回答