查找具有最大可能总和的子矩阵 O(n^2)
我正在尝试用 Java 编写一个程序，当给定一个 MxN 矩阵时，它将找到具有最大数字和的（连续）子矩阵。然后程序需要返回子矩阵的左上角坐标和右下角坐标。矩阵可以包含负数，并且矩阵和子矩阵都不需要是正方形。
我看到这里讨论了这个问题：获取具有最大和的子矩阵？和那里的解决方案似乎是 O(n^3)。我的一个朋友说他们曾经成功地在 O(n^2) 内解决了这个问题。还建议这里。这可能吗？
是否有任何可用的代码可以以最有效的方式解决这个问题？
I'm trying to write a program in Java that when given an MxN matrix it will find the (contiguous) submatrix with the biggest sum of numbers. The program then needs to return the top left corner coordinates of the submatrix and the bottom right corner coordinates. The matrix can include negative numbers and both the matrix and submatrix don't need to be square.
I saw that this was discussed here: Getting the submatrix with maximum sum? and the solution there seems to be O(n^3). A friend of mine said that they had once managed to solve this problem in O(n^2). Also suggested here. Is that possible?
Is there any available code out there that solves this problem in the most efficient way?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您（很可能）无法在
O(n^2)内解决您的问题，至少没有这样的算法是已知的。最佳解决方案的复杂度为次立方，但实现起来非常困难，而且在实践中可能会更慢。您可以在此处阅读有关它的论文。通常使用的算法是您发现的问题中引用的
O(n^3)算法。You (most likely) can't solve your problem in
O(n^2), at least no such algorithm is known. The optimal solution has sub-cubic complexity, but it's very hard to implement and probably slower in practice. You can read a paper about it here.The usual algorithm used is the
O(n^3)one referenced in the question you found.(S)他是你的朋友..所以只要问他/她，并与我们分享:)
(S)He's a friend of yours.. so just ask him/her, and do share with us too :)