输入:二维数组NxN - 矩阵 - 具有正负元素.
输出:任何大小的子矩阵,使得其总和是所有可能子矩阵中的最大值.
要求:算法复杂度为O(N ^ 3)
历史:在Algorithmist,Larry和Kadane算法的修改的帮助下,我设法解决了部分问题,即仅在Java中确定求和.
感谢Ernesto设法解决问题的其余部分,即确定矩阵的边界,即左上角,右下角 - 在Ruby下面.
我有一个N*N矩阵(N = 2到10000)的数字,范围从0到1000.如何找到由相同数字组成的最大(矩形)子矩阵？
例:
1 2 3 4 5
-- -- -- -- --
1 | 10 9 9 9 80
2 | 5 9 9 9 10
3 | 85 86 54 45 45
4 | 15 21 5 1 0
5 | 5 6 88 11 10
输出应该是子矩阵的区域,后面是其左上角元素的基于1的坐标.例如,这是(6, 2, 1)因为有6个9位于第2列第1行.