# Dynamic Programming – Maximum size square sub-matrix with all 1s

Objective: Given a matrix of 0’s and 1’s (binary matrix). Find out Maximum size square sub-matrix with all 1’s.

Example:

Approach:

Base Cases:

• If only one row is given then cells with 1’s will be the Maximum size square sub-matrix with size = 1.
• If only one column is given then cells with 1’s will be the Maximum size square sub-matrix with size = 1.

Dynamic Programming (Bottom-up).

• Create an auxiliary array of the same size as given input array. We will fill the auxiliary array with Maximum size square sub-matrix with all 1’s possible with respect to the particular cell.
• Once the auxiliary is fill, scan it and find out the maximum entry in it, this will the size of Maximum size square sub-matrix with all 1’s in the given matrix.

How to fill the auxiliary matrix??

• Copy the first row and first column from the given array to auxiliary array. (Read the base cases described earlier).
• For filling rest of cells, check if particular cell’s value is 0 in given array, if yes then put 0 against to that cell in auxiliary array.
• check if particular cell’s value is 1 in given array, if yes then put Minimum (value in the left cell, top cell and left-top diagonal cell) + 1 in auxiliary cell.

Recursive Equation:

```For Given arrA[][], create auxiliary array sub[][].
```

#### Base Cases: sub[i] = arrA[i] i = 0 to row Count // copy the first column sub[i] = arrA[i] i = 0 to column Count // copy the first row

for rest of the cells
sub[i][j] = 0 if arrA[i][j]=0               = Min(arrA[i-1][j], arrA[i][j-1], arrA[i-1][j-1] )
At the End, scan the sub[][] and find out the maximum entry in it.

Example:

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
```Output: