研发埠
标题:
[算法题] 找最大子矩阵
[打印本页]
作者:
王培培
时间:
2013-8-16 10:15
标题:
[算法题] 找最大子矩阵
求一个二维矩阵中最大的子矩阵(元素和最大).如:1 2 0 -3 4-2 3 4 5 -11 1 5 3 0中最大的是:3 4 51 5 3要求
1)写出算法;(2)分析时间复杂度;
作者:
王鹏
时间:
2013-8-16 10:26
思路是:加入对于一个一维数组,可以在O(n)的时间复杂度内求出最大的sub array和.这题的关键就是把一维数组扩展到二维数组,不同的地方就是宽不止一行.用一个二维数组M[n][n]来记录,比如M
[j][k]代表从第i行开始,宽度为j行的伪一维数组(列元素值为对应列宽度上所有元素值之和)在k列上的值.由于一共有O(n*n)各伪一维数组,每个需要O(n)的时间复杂度求最大subarray,总时间复杂度是O(n^3)
欢迎光临 研发埠 (http://bbs.yanfabu.com/)
Powered by Discuz! X3.2
1)写出算法;(2)分析时间复杂度;