我正在尝试用Java编写一个程序，当给出MxN矩阵时，它将找到具有最大数字和的（连续）子矩阵。然后，程序需要返回子矩阵的左上角坐标和右下角坐标。矩阵可以包含负数，矩阵和子矩阵都不必为正方形。
我看到这里讨论了这一点：获得最大和的子矩阵？并且解决方案似乎是O（n^3）。我的一个朋友说他们曾经设法在O（n ^2）中解决这个问题。[
是否有可用的代码以最有效的方式解决此问题？
您（很可能）无法解决中的问题O(n^2)，至少没有这样的算法是已知的。最佳解决方案具有亚立方的复杂性，但是很难实施，并且在实践中可能会变慢。您可以在这里阅读有关它的论文。
O(n^2)
使用的常用算法是O(n^3)您发现的问题中引用的算法。
O(n^3)
