我有一个边长为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 x n的子矩阵,其中1的数量最多。
我已经找到了各种方法来实现它,但没有一种比O(n^4)更快的方法。我还发现了更快的方法,但是不需要子矩阵必须是n x n。
编辑: 子矩阵必须是连续的。
我有一个边长为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 x n的子矩阵,其中1的数量最多。
我已经找到了各种方法来实现它,但没有一种比O(n^4)更快的方法。我还发现了更快的方法,但是不需要子矩阵必须是n x 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]
。