### Question

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)

### Solution

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
```