# Maximum size Square sub-with all 1’s in C++

In this tutorial, we are going to discuss how to find maximum square sub-matrix with all 1’s and its size in a given binary matrix in C++. We will use a dynamic programming approach to solve this problem.

What is Dynamic Programming?

Dynamic programming is an approach to solve the complex problem by breaking down into simple sub-problems and store the result of sub-problems for future use. We use DP basically when we have to use a recursive approach for a problem and there is a need to calculate the result of the same sub-problem again and again.

Step by Step Approach

• Take two input n and m as rows and columns of input matrix.
• Input 2-D binary matrix a[][] of size n*m.
• Take an auxiliary 2-D matrix b[][] of size n*m.
• Now, input elements of 1st row and 1st column of a[][] as it is in matrix b[][].
• Now, fill rest of matrix b[][] as

## find maximum square sub-matrix with all 1’s in C++

check every possible square 2*2 matrix and find minimum element among top-left, top-right, bottom-left element and find fill bottom-right element as min. among 3 + 1 else fill the value 0.

Code Snippet:-

```if(a[i][j] == 1)
b[i][j] = min(b[i][j-1],min(b[i-1][j], b[i-1][j-1])) + 1;
else
b[i][j] = 0;

```
• Check for maximum value in matrix b[][] and store it in max_num and that row value in max_i and column in max_j.
• To print the max square sub-matrix of 1’s backtrack from max_i,max_j and print matrix of max_num*max_num.

### C++ Code implementation of maximum square sub-matrix with 1’s

```#include<bits/stdc++.h>

using namespace std;

int a;

void solve(long long n, long long m)
{
int i,j;
int b;

for(i = 0; i < n; i++)
b[i] = a[i];

for(j = 0; j < m; j++)
b[j] = a[j];

for(i = 1; i < n; i++)
{
for(j = 1; j < m; j++)
{
if(a[i][j] == 1)
b[i][j] = min(b[i][j-1],min(b[i-1][j], b[i-1][j-1])) + 1;

else
b[i][j] = 0;
}
}

int max_num = b, max_i = 0, max_j = 0;

for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
if(max_num < b[i][j])
{
max_num = b[i][j];
max_i = i;
max_j = j;
}
}
}

cout<<"Maximum size of Sub-matrix with 1's is : "<<max_num<<"*"<<max_num<<endl;

cout<<"\n Max Square sub-matrix with 1's is :"<<endl;

for(i = max_i; i > max_i - max_num; i--)
{
for(j = max_j; j > max_j - max_num; j--)
{
cout<<a[i][j];
}
cout<<endl;
}
}

int main()
{
long long i,j,n,m;

cin>>n>>m;

for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
cin>>a[i][j];
}

solve(n,m);
}```

INPUT

```8 8
1 1 0 0 1 1 0 1
1 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1```

OUTPUT

```Maximum size of Sub-matrix with 1's is : 4*4

Max Square sub-matrix with 1's is :
1111
1111
1111
1111```