我的代码,复杂度O(m^2*n),根据programming pearls上的hints int getMaxSubMatrix(int a[][], int m, int n) { int sum = 0; int max = MIN_INTEGER; int row_sum; for(col_i=0; col_i{ for(col_j=0; col_j<=col_i; col_j++) { for(row=0; row{ row_sum = get_sum(row, col_i, col_j); if(sum < 0) sum = row_sum; else sum+= row_sum; max = max} } } return max; }
看了一下pearls, 觉得之前讨论的那个DP公式还是对的,跟pearls的预处理有同样的 效果。。 Define m(k,i,j) to be the maximum sum submatrix ending with the line A[k,i.. j]. (k is the row number, i, j is the left and right column number) then the DP formula is m(k,i,j)=max{ 0, m(k-1,i,j)+sum{A[k,i..j]}} 注意到 m(k,1,j)其实就是第k行中从左到第j列的所有和,跟预处理的效果一样。。 你的这个例子,得到的 m(1, i,j) m(2, i,j), m(3, i, j)分别为: (只考虑i<=j的情况) 0 0 0 0 1 3 3 5 3 2 1 1 4 7 4 4 1 0 最大和是7, m(3,1,2)也就是以第3行,第一列到第二列为最下面一条边的矩形。通过 backtrack应该可以找到前面的。。