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 0 1 1 1 1 1 0 0 0 0 0
The maximum square sub-matrix with all set bits is size 9. Note we only find square, not rectangles! (this makes it much easier)
Since square only, we can use DP. Quoted answer below:
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] where M[i][j] is the rightmost and bottommost entry in sub-matrix.
Construct a sum matrix S[R][C] for the given M[R][C].
Copy first row and first columns as it is from M to S
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