[回复]
[修改] [删除]
[返回版面]
|
1 |
作者: admin, 讨论版: 算法集锦, 发表时间: 2014-01-05 12:35:33 PST
标题: 最大子矩阵
关键字:
1. 任给一0/1矩阵M[m][n], 求最大全1子矩阵.
答案可以由推广"直方图下最大矩形"得到. 复杂度O(mn). [this is wrong: O(min(m^2*n, n^2*m)).]
2. 任给一0/1矩阵M[m][n], 求最大全1子正方形矩阵.
解法为DP.
- 构造另一个矩阵int V[m][n]. 第一行和第一列于M相同.
- 若M[x][y] == 0, V[x][y] = 0;
否则, V[x][y] = min(V[x-1][y-1], V[x][y-1], V[x-1][y]).
例如:
0 1 1 0 1 1
1 1 1 => 1 1 2
1 1 1 1 2 2
1 1 0 1 1 0
1 1 1 => 1 2 1
1 1 1 1 2 2
3. 任给一整数矩阵, 求和最大子矩阵
可以由推广Kadane和的算法给出结果. 复杂度O(min(m^2*n, n^2*m)).
--
最后修改: admin on 2015-01-27 00:45:20 PST
※ 来源: homecox.com [来自: 66.]
|
|
|