Dynamic programming - Largest square block

Question

I need to find the largest square of 1's in a giant file full of 1's and 0's. I know i have to use dynamic programming. I am storing it in a 2D array. Any help with the algorithm to find the largest square would be great, thanks!

example input:

1 0 1 0 1 0
1 0 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 1
1 1 1 1 1 1

answer:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

My code so far:

int Square (Sq[int x][int y]) {
   if (Sq[x][y]) == 0) {
       return 0;
   }
   else {
       return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
   }
}

(assuming values already entered into the array)

int main() {
    int Sq[5][6]; //5,6 = bottom right conner
    int X = Square(Sq[5][6]);
}

How do I go on from there?

Answer 1

Let N be the amount of cells in the 2D array. There exists a very efficient algorithm to list all the maximum empty rectangles. The largest empty square is inside one of these empty rectangles, and founding it is trivial once the list of the maximum empty rectangles has been computed. A paper presenting a O(N) algorithm to create such a list can be found at www.ulg.ac.be/telecom/rectangles as well as source code (not optimized). Note that a proof exists (see the paper) that the number of largest empty rectangles is bounded by N. Therefore, selecting the largest empty square can be done in O(N), and the overall method is also O(N). In practice, this method is very fast. The implementation is very easy to do, since the whole code should not be more than 40 lines of C (the algorithm to list all the maximum empty rectangles takes about 30 lines of C).