[算法题] 找最大子矩阵

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

思路是:加入对于一个一维数组,可以在O(n)的时间复杂度内求出最大的sub array和.这题的关键就是把一维数组扩展到二维数组,不同的地方就是宽不止一行.用一个二维数组M[n][n]来记录,比如M[j][k]代表从第i行开始,宽度为j行的伪一维数组(列元素值为对应列宽度上所有元素值之和)在k列上的值.由于一共有O(n*n)各伪一维数组,每个需要O(n)的时间复杂度求最大subarray,总时间复杂度是O(n^3)