Today we are going to share a Python3 code for Maximum size square sub-matrix with all 1s. If you are a python beginner and want to start learning the python programming, then keep your close attention in this tutorial as I am going to share a Python3 code for Maximum size square sub-matrix with all 1s.
To increase your Python knowledge, practice all Python programs, here is a collection of 100+ Python problems with solutions.
Copy the below python program and execute it with the help of python compiler.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | def printMaxSubSquare(M): R = len(M) # no. of rows in M[][] C = len(M[0]) # no. of columns in M[][] S = [[0 for k in range(C)] for l in range(R)] # here we have set the first row and column of S[][] # Construct other entries for i in range(1, R): for j in range(1, C): if (M[i][j] == 1): S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 else: S[i][j] = 0 # Find the maximum entry and # indices of maximum entry in S[][] max_of_s = S[0][0] max_i = 0 max_j = 0 for i in range(R): for j in range(C): if (max_of_s < S[i][j]): max_of_s = S[i][j] max_i = i max_j = j print("Maximum size sub-matrix is: ") for i in range(max_i, max_i - max_of_s, -1): for j in range(max_j, max_j - max_of_s, -1): print (M[i][j], end = " ") print("") # Driver Program M = [[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]] printMaxSubSquare(M) |
Maximum size sub-matrix is:
1 1 1
1 1 1
1 1 1
