Be the first user to complete this post

Add to List 
Dynamic Programming  Maximum size square submatrix with all 1s
Objective: Given a matrix of 0's and 1's (binary matrix). Find out the Maximum size square submatrix 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 submatrix with size = 1.
 If only one column is given then cells with 1's will be the Maximum size square submatrix with size = 1.
Dynamic Programming (Bottomup).
 Create an auxiliary array of the same size as the given input array. We will fill the auxiliary array with Maximum size square submatrix with all 1's possible with respect to the particular cell.
 Once the auxiliary is filled, scan it and find out the maximum entry in it, this will be the size of the Maximum size square submatrix 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 the auxiliary array. (Read the base cases described earlier).
 For filling the rest of the cells, check if a particular cell's value is 0 in the given array, if yes then put 0 against that cell in the auxiliary array.
 check if a particular cell's value is 1 in the given array, if yes then put Minimum (value in the left cell, top cell, and lefttop diagonal cell) + 1 in the auxiliary cell.
Recursive Equation:
For Given arrA[][], create auxiliary array sub[][].
Base Cases:
sub[i][0] = arrA[i][0] i = 0 to row Count // copy the first column
sub[0][i] = arrA[0][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[i1][j], arrA[i][j1], arrA[i1][j1] )
At the End, scan the sub[][] and find out the maximum entry in it.
Example:
Code:
Output:
Output: Maximum size square submatrix with all 1s: 3
Also Read: