# Finding the densest n * n submatrix in a sparse matrix

I have a sparse square matrix with a side of 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 the n * n submatrix with the largest number of 1s.

I found several ways to do this, but not faster than O (n ^ 4). I also found faster ways without requiring the submatrix to be n * n.

EDIT: The submatrix must be contiguous,

source to share

Based on your application for an O (n ^ 4) -time algorithm, my guess is that the submatrix must be contiguous, since otherwise the problem is NP-hard (it's harder than biclik detection). For the O (n ^ 2) -time algorithm, it suffices to perform O (n ^ 2) preprocessing, which allows 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 an array `X[1..m,1..n]`

, compute the 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 calculate `sum_{i=a}^b sum_{j=c}^d X[i,j]`

, use the inclusion of exception `Y[c,d] - Y[a-1,d] - Y[c,b-1] + Y[a-1,b-1]`

.

source to share