Mei*_*eir 3 algorithm submatrix
我正在尝试用Java编写一个程序,当给定一个MxN矩阵时,它会找到具有最大数字总和的(连续的)子矩阵.然后程序需要返回子矩阵的左上角坐标和右下角坐标.矩阵可以包括负数,矩阵和子矩阵都不需要是正方形.
我在这里讨论过这个问题:获得最大总和的子矩阵？并且那里的解决方案似乎是O(n ^ 3).我的一个朋友说他们曾经设法在O(n ^ 2)中解决了这个问题.这里也建议.那可能吗？
有没有可用的代码以最有效的方式解决这个问题？
IVl*_*lad 7
你(很可能)无法解决你的问题O(n^2),至少没有这样的算法.最优解决方案具有亚立方复杂性,但实现起来非常困难,实际上可能更慢.你可以在这里阅读一篇关于它的论文.
O(n^2)
使用的常用算法是O(n^3)您找到的问题中引用的算法.
O(n^3)
小智 5
（S）他是您的朋友..所以只要问问他/她，并与我们分享:)
归档时间：
15 年，8 月 前
查看次数：
4133 次
最近记录：