Finding the most dense n*n sub matrix in a sparse matrix

Question

I have a sparse square matrix with the side 2*n.

eg.

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

And i need an efficient way to find a sub matrix with a size of n*n with the largest amount of 1s.

I have found various ways to do it but none faster then O(n^4). I've also found faster ways without the requirement that the sub matrix needs to be n*n.

EDIT: The submatrix has to be contiguous,

Answer 1

Based on your claim of an O(n^4)-time algorithm, I'm assuming that the submatrix has to be contiguous, as otherwise the problem is NP-hard (it's harder than detecting a biclique). For an O(n^2)-time algorithm, it suffices to do O(n^2)-time preprocessing that enables O(1)-time queries of the form "given a, b, c, d, compute sum_{i=a}^b sum_{j=c}^d X[i,j]".

Given the array X[1..m,1..n], compute an array Y[0..m,0..n] as follows.

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

Now, Y[c,d] = sum_{i=1}^c sum_{j=1}^d X[i,j]. To compute sum_{i=a}^b sum_{j=c}^d X[i,j], use inclusion-exclusion: Y[c,d] - Y[a-1,d] - Y[c,b-1] + Y[a-1,b-1].