Maximum sub | C ++ implementation to find the maximum area sub - matrix having count of 1 ' s ▁ one ▁ more ▁ than ▁ count ▁ of ▁ 0' s ; function to find the length of longest subarray having count of 1 ' s ▁ one ▁ more ▁ than ▁ count ▁ of ▁ 0' s ; unordered_map ' um ' implemented as hash table ; traverse the given array ; accumulating sum ; when subarray starts form index '0' ; make an entry for ' sum ' if it is not present in ' um ' ; check if ' sum - 1' is present in ' um ' or not ; update ' start ' , ' finish ' and maxLength ; required maximum length ; function to find the maximum area sub - matrix having count of 1 ' s ▁ one ▁ more ▁ than ▁ count ▁ of ▁ 0' s ; variables to store final and intermediate results ; set the left column ; Initialize all elements of temp as 0 ; Set the right column for the left column set by outer loop ; Calculate sum between current left and right for every row ' i ' , consider '0' as ' - 1' ; function to set the ' start ' and ' finish ' variables having index values of temp [ ] which contains the longest subarray of temp [ ] having count of 1 ' s ▁ ▁ one ▁ more ▁ than ▁ count ▁ of ▁ 0' s ; Compare with maximum area so far and accordingly update the final variables ; Print final values ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define SIZE  10 NEW_LINE int lenOfLongSubarr ( int arr [ ] , int n , int & start , int & finish ) { unordered_map < int , int > um ; int sum = 0 , maxLen = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; if ( sum == 1 ) { start = 0 ; finish = i ; maxLen = i + 1 ; } else if ( um . find ( sum ) == um . end ( ) ) um [ sum ] = i ; if ( um . find ( sum - 1 ) != um . end ( ) ) { if ( maxLen < ( i - um [ sum - 1 ] ) ) start = um [ sum - 1 ] + 1 ; finish = i ; maxLen = i - um [ sum - 1 ] ; } } return maxLen ; } void largestSubmatrix ( int mat [ SIZE ] [ SIZE ] , int n ) { int finalLeft , finalRight , finalTop , finalBottom ; int temp [ n ] , maxArea = 0 , len , start , finish ; for ( int left = 0 ; left < n ; left ++ ) { memset ( temp , 0 , sizeof ( temp ) ) ; for ( int right = left ; right < n ; right ++ ) { for ( int i = 0 ; i < n ; ++ i ) temp [ i ] += mat [ i ] [ right ] == 0 ? -1 : 1 ; len = lenOfLongSubarr ( temp , n , start , finish ) ; if ( ( len != 0 ) && ( maxArea < ( finish - start + 1 ) * ( right - left + 1 ) ) ) { finalLeft = left ; finalRight = right ; finalTop = start ; finalBottom = finish ; maxArea = ( finish - start + 1 ) * ( right - left + 1 ) ; } } } cout << " ( Top , ▁ Left ) : ▁ ( " << finalTop << " , ▁ " << finalLeft << " ) STRNEWLINE " ; cout << " ( Bottom , ▁ Right ) : ▁ ( " << finalBottom << " , ▁ " << finalRight << " ) STRNEWLINE " ; cout << " Maximum ▁ area : ▁ " << maxArea ; } int main ( ) { int mat [ SIZE ] [ SIZE ] = { { 1 , 0 , 0 , 1 } , { 0 , 1 , 1 , 1 } , { 1 , 0 , 0 , 0 } , { 0 , 1 , 0 , 1 } } ; int n = 4 ; largestSubmatrix ( mat , n ) ; return 0 ; }