Maximum submatrix

a) There is a square of nxn size which is comprised of n-square 1x1 squares. Some of these 1x1 squares are colored. Find the biggest subsquare which is not colored.

b) Also asked to extend it to find the biggest area rectangle.

OR

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  1  1  1
   1  1  1  1  1
   0  0  0  0  0
The maximum square sub-matrix with all set bits is

    1  1  1
    1  1  1
    1  1  1

Approach:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
     a) Copy first row and first columns as it is from M[][] to S[][]
     b) For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
   sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  1
   1  2  2  3  2
   0  0  0  0  0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.

To find the biggest rectangle:
R0   0  1  1  0  1
R1   1  1  0  1  0
R2   0  1  1  1  1
R3   1  1  1  1  1
R4   1  1  1  1  1
R5   0  0  0  0  0

Rij denote Ri & Rj
R01 = 0 1 0 0 0 (max area of rect so far: 1*2 = 2)
R12 = 0 1 0 1 0 (max area of rect so far: 1*2 = 2)
R23 = 0 1 1 1 1 (max area of rect so far: 4*2 = 8)
R34 = 1 1 1 1 1 (max area of rect so far: 5*2 = 10)
R45 = 0 0 0 0 0  (max area of rect so far: 10)

Again lets do the same & operation between consecutive rows above.

R02 = 0 1 0 0 0 (local area: 1*3=3, max so far: 10)
R13 = 0 1 0 1 0 (local area: 1*3=3, max so far: 10)
R24 = 0 1 1 1 1 (local area: 4*3=12, new max so far: 12)
R35 = 0 0 0 0 0 (local area: 0*0=0, new max so far: 12)

R03 = 0 1 0 0 0 (max so far: 12)
R14 = 0 1 0 1 0 (max so far: 12)
R25 = 0 0 0 0 0 (max so far: 12)

again repeat
R04 = 0 1 0 0 0 (max so far: 12)
R15 = 0 0 0 0 0 (max so far: 12)

finally,
R05 = 0 0 0 0 0

And max area of rectangle so far = 12.