在稀疏矩阵中找到最密集的n * n子矩阵

Question

我的侧面是2 * n的稀疏方阵。

例如。

1,0,0,1,0,1
0,1,1,1,0,1
1,0,0,0,1,1
0,0,1,1,0,0
1,1,1,0,0,0
0,0,0,1,1,0

我需要一种有效的方法来找到大小为n * n且最大数量为1s的子矩阵。

我已经找到了各种方法来做到这一点，但是没有比O（n ^ 4）更快的方法。我还发现了更快的方法，而无需子矩阵需要为n * n。

编辑：子矩阵必须是连续的，

Answer 1

根据您对 O(n^4) 时间算法的主张，我假设子矩阵必须是连续的，否则问题是 NP 难的（它比检测 biclique 更难）。对于 O(n^2) 时间算法，只需执行 O(n^2) 时间预处理即可实现“given a, b, c, d,compute sum_{i=a}^b sum_{j=c}^d X[i,j]”形式的 O(1) 时间查询。

给定数组X[1..m,1..n]，按如下方式计算数组Y[0..m,0..n]。

initialize Y to the zero array
for i from 1 to m
    for j from 1 to n
       Y[i,j] = Y[i-1,j] + X[i,j]
    end
end
for i from 1 to m
    for j from 1 to n
       Y[i,j] = Y[i,j-1] + Y[i,j]
    end
end

现在，Y[c,d] = sum_{i=1}^c sum_{j=1}^d X[i,j]。要计算sum_{i=a}^b sum_{j=c}^d X[i,j]，请使用包含-排除：Y[c,d] - Y[a-1,d] - Y[c,b-1] + Y[a-1,b-1]。