Largest Submatrix of All 1’s

Description

Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.

Input

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 2000) on line. Then come the elements of a (0,1)-matrix in row-major order on m lines each with n numbers. The input ends once EOF is met.

Output

For each test case, output one line containing the number of elements of the largest submatrix of all 1’s. If the given matrix is of all 0’s, output 0.

Sample Input

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
Sample Output

0
4

Solution

We reduce the complexity of checking each rectangle to constant time using the integral image: http://en.wikipedia.org/wiki/Summed_area_table
The complexity is O(m*n*m*n).

We first create the integral image.  The value at any point (x, y) in the summed area table is just the sum of all the points above and to the left of (x, y), inclusive


// two dimensional input matrix, m is the number of rows, n is the number of columns.
// two dimensional output integral image

int ** createIntegralImage(int** input, int m, int n){
if(m<1 || n<1){
return NULL:
}
// allocate the output matrix
int** output=new int*[m];
for(int i=0;i<m;++i){
output[i]=new int[n];
}
// generate entries
output[0][0]=input[0][0];
// fill the first row
for(int i=1;i<n;++i){
output[0][i]=output[0][i-1]+input[0][i];
}
// fill the first column
for(int i=1;i<m;++i){
output[i][0]=output[i-1][0]+input[i][0];
}
// fill the rest
for(int i=1;i<m;++i){
for(int j=1;j<n;++j){
output[i][j]=output[i-1][j]+ouput[i][j-1]-output[i-1][j-1]+input[i][j];
}
}
return output;
}

int main(int argc, char* argv[]){
// assume we have the input processed
std::vector<int> array;
int** integralImage=createIntegralImage(input,m,n);
for(int i=0;i<m-1;++i){
for(int j=0;j<n-1;++j){
// i,j is the top left corner of the rectangle
for(int x=j+1;x<n;++x){
for(int y=i+1;y<m;++y){
// x,y is the bottom right corner of the rectangle
array.push_back(integralImage[y][x]+integralImage[i][j]-integralImage[y][j]-integralImage[i][x]);
}
}
}
}
std::cout<<*std::max_element(array.begin(),array.end())<<std::endl;
return 0;
}