Dynamic programming implementation of maximum size square sub-matrix with all 1's

DynamicMaxOnesMatrixSize.cpp

#include <bits/stdc++.h>
using namespace std;

int findMaxOnesMatrixSize(vector<vector<int> > &matrix){

	int n = matrix.size();
	int m = matrix[0].size();

	// Initializing dp matrix with 0 ........
	vector<vector<int> > dp(n, vector<int>(m,0));
	int maxOnesMatrixSize = 0;

	for(int i = 0 ; i < n ; i ++){

		for(int j = 0 ; j < m ; j ++){

			if(matrix[i][j] == 0){

				// If the current block has zero no need to do any computation ...........
				continue;

			}

			int upperMatrixSize = 0, diagonalMatrixSize = 0, sideMatrixSize = 0;

			if(i > 0){

				// Updating upper matrix size ............
				upperMatrixSize = dp[i - 1][j];

			}

			if(j > 0){

				// Updating side matrix size ............
				sideMatrixSize = dp[i][j - 1];

			}

			if(i > 0 && j > 0){

				// Updating diagonal matrix size ...........
				diagonalMatrixSize = dp[i - 1][j - 1];

			}

			dp[i][j] = 1 + min(diagonalMatrixSize,min(upperMatrixSize,sideMatrixSize));
			maxOnesMatrixSize = max(maxOnesMatrixSize,dp[i][j]);

		}

	}

	return maxOnesMatrixSize;

}

// Driver function ...........
int main(){

	int n,m;
	cin >> n >> m;

	vector<vector<int> > matrix(n,vector<int> (m));

	for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < m ; j ++)
			cin >> matrix[i][j];

	cout << findMaxOnesMatrixSize(matrix) << endl;

}