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