我正在尝试用Java编写一个程序,当给定一个MxN矩阵时,它将找到数字和最大的(连续的)子矩阵。然后程序需要返回子矩阵的左上角坐标和右下角坐标。矩阵可以包含负数,且矩阵和子矩阵都不需要是正方形。
我看到这个问题在这里已经被讨论过:Getting the submatrix with maximum sum?,那里的解决方案似乎是O(n^3)。我的朋友说他们曾经成功地用O(n^2)解决了这个问题。也可以在这里找到相关信息。 这种问题有没有最有效的可用代码呢?
我看到这个问题在这里已经被讨论过:Getting the submatrix with maximum sum?,那里的解决方案似乎是O(n^3)。我的朋友说他们曾经成功地用O(n^2)解决了这个问题。也可以在这里找到相关信息。 这种问题有没有最有效的可用代码呢?