欢迎访问
讨论版列表 - 算法集锦 - 主题数: 41 | 文章数: 47 | 管理员: homecox

算法集锦

版面 | 文摘区 | 马克区

文章数: 1 | 分页: << 1 >>
admin
[回复] [修改] [删除] [返回版面] 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.]


Reply

Please log in first.