找最大子矩阵 （哪家的我忘了）

求一个二维矩阵中最大的子矩阵(元素和最大).如:
1  2 0 -3 4
-2 3 4 5 -1
1  1 5 3  0
中最大的是:
3 4 5
1 5 3
要求:(1)写出算法;(2)分析时间复杂度;

这个题naive的解法就是4*m*n，m和n是矩阵的dimension。

可以做一些result cache，另外构建一个矩阵t[m][n], t[i][j] = sum(a[0][0]+a[0][1]+a[1][0]+..a[i][j])，这也是o(m*n)，但是常数项小了

这个题naive的解法就是4*m*n，m和n是矩阵的dimension。

可以做一些result cache，另外构建一个矩阵t[m][n], t[j] = sum(a[0][0]+a[0][1]+a[1][0]+..a[j])，这也是o(m*n)，但是常数项小了
MontagueHu 发表于 2011-7-1 08:44

    为什么是4×m×n？？
    brutal force应该是m*n*m*n吧，你想想，start point 有m*n种选择，dimension有m*n种选择

题目不是二维矩阵，如果是m*n维度的，为什么不是整个矩阵的和最大？

anyway，思路大概是这样，given一个一维矩阵，找到[i...j]，使得a[i]+...a[j]最大，这是o(n)的，参考programming perls。

扩展到2维矩阵是brute force，o(n3)

题目不是二维矩阵，如果是m*n维度的，为什么不是整个矩阵的和最大？

anyway，思路大概是这样，given一个一维矩阵，找到，使得a+...a[j]最大，这是o(n)的，参考programming perls。

扩展到2维矩阵是brute force，o(n3)
MontagueHu 发表于 2011-7-3 01:33

    晕，题目弄错了，修改成二维矩阵求最大子矩阵，矩阵元素有正有负

那就是o(n3)，经典题是在一维子矩阵（有正有负）找出和最大的a[i]+...a[j]，这个是O(n)

思路是:
加入对于一个一维数组,可以在O(n)的时间复杂度内求出最大的sub array和.
这题的关键就是把一维数组扩展到二维数组,不同的地方就是宽不止一行.

用一个二维数组M[n][n]来记录,比如M[i][j][k]代表从第i行开始,宽度为j行的伪一维数组(列元素值为对应列宽度上所有元素值之和)在k列上的值.由于一共有O(n*n)各伪一维数组,每个需要O(n)的时间复杂度求最大subarray,总时间复杂度是O(n^3)

M * M * N, from programming pearl

这一题的最大子矩阵和应该是
1  2 0 -3 4
-2 3 4 5 -1
1  1 5 3  0；23吧~

wwwyhx 发表于 2011-7-10 17:31
思路是:
加入对于一个一维数组,可以在O(n)的时间复杂度内求出最大的sub array和.
这题的关键就是把一维数 ...

用一个一维数组记录就好了，careercup上的程序，非常tricky，我写了两遍，打算深深的记住它~
https://github.com/johnwan/maxSubMatrix/blob/master/.gitignore