Largest possible square submatrix with maximum AND value | C ++ program to find the length of longest possible square submatrix with maximum AND value from the given matrix ; Function to calculate and return the length of square submatrix with maximum AND value ; Extract dimensions ; 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 Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MAX_value ( vector < vector < int > > arr ) { int row = arr . size ( ) ; int col = arr [ 0 ] . size ( ) ; int dp [ row ] [ col ] ; memset ( dp , sizeof ( dp ) , 0 ) ; int i = 0 , j = 0 ; int c = arr [ 0 ] [ 0 ] , p = 0 ; int d = row ; for ( i = 0 ; i < d ; i ++ ) { for ( j = 0 ; j < d ; j ++ ) { if ( c < arr [ i ] [ j ] ) { c = arr [ i ] [ j ] ; } if ( i == 0 j == 0 ) { dp [ i ] [ j ] = 1 ; } else { if ( arr [ i - 1 ] [ j - 1 ] == arr [ i ] [ j ] && arr [ i - 1 ] [ j ] == arr [ i ] [ j ] && arr [ i ] [ j - 1 ] == arr [ i ] [ j ] ) { dp [ i ] [ j ] = min ( dp [ i - 1 ] [ j - 1 ] , min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ) + 1 ; } else { dp [ i ] [ j ] = 1 ; } } } } for ( i = 0 ; i < d ; i ++ ) { for ( j = 0 ; j < d ; j ++ ) { if ( arr [ i ] [ j ] == c ) { if ( p < dp [ i ] [ j ] ) { p = dp [ i ] [ j ] ; } } } } return p * p ; } int main ( ) { vector < vector < int > > 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 } } ; cout << MAX_value ( arr ) << endl ; return 0 ; }