Largest possible square submatrix with maximum AND value | Function to calculate and return the length of square submatrix with maximum AND value ; Extract dimensions ; Auxiliary array Initialize auxiliary array ; c : Stores the maximum value in the matrix p : Stores the number of elements in the submatrix having maximum AND value ; Iterate over the matrix to fill the auxiliary matrix ; Find the max element in the matrix side by side ; Fill first row and column with 1 's ; For every cell , check if the elements at the left , top and top left cells from the current cell are equal or not ; Store the minimum possible submatrix size these elements are part of ; Store 1 otherwise ; Checking maximum value ; If the maximum AND value occurs more than once ; Update the maximum size of submatrix ; Final output ; Driver Code
def MAX_value ( arr ) : NEW_LINE INDENT row = len ( arr ) NEW_LINE col = len ( arr ) NEW_LINE dp = [ [ 0 for i in range ( col ) ] for j in range ( row ) ] NEW_LINE i , j = 0 , 0 NEW_LINE c , p = arr [ 0 ] [ 0 ] , 0 NEW_LINE d = row NEW_LINE for i in range ( d ) : NEW_LINE INDENT for j in range ( d ) : NEW_LINE INDENT if ( c < arr [ i ] [ j ] ) : NEW_LINE INDENT c = arr [ i ] [ j ] NEW_LINE DEDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( arr [ i - 1 ] [ j - 1 ] == arr [ i ] [ j ] and arr [ i - 1 ] [ j ] == arr [ i ] [ j ] and arr [ i ] [ j - 1 ] == arr [ i ] [ j ] ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i - 1 ] [ j - 1 ] , min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ) + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( d ) : NEW_LINE INDENT for j in range ( d ) : NEW_LINE INDENT if ( arr [ i ] [ j ] == c ) : NEW_LINE INDENT if ( p < dp [ i ] [ j ] ) : NEW_LINE INDENT p = dp [ i ] [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT return p * p NEW_LINE DEDENT arr = [ [ 9 , 9 , 3 , 3 , 4 , 4 ] , [ 9 , 9 , 7 , 7 , 7 , 4 ] , [ 1 , 2 , 7 , 7 , 7 , 4 ] , [ 4 , 4 , 7 , 7 , 7 , 4 ] , [ 5 , 5 , 1 , 1 , 2 , 7 ] , [ 2 , 7 , 1 , 1 , 4 , 4 ] ] NEW_LINE print ( MAX_value ( arr ) ) NEW_LINE