Maximum sub | Java 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
import java . util . * ; class GFG { static int start , finish ; static int lenOfLongSubarr ( int [ ] arr , int n ) { HashMap < Integer , Integer > um = new HashMap < Integer , Integer > ( ) ; 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 . containsKey ( sum ) ) um . put ( sum , i ) ; if ( um . containsKey ( sum - 1 ) ) { if ( maxLen < ( i - um . get ( sum - 1 ) ) ) start = um . get ( sum - 1 ) + 1 ; finish = i ; maxLen = i - um . get ( sum - 1 ) ; } } return maxLen ; } static void largestSubmatrix ( int [ ] [ ] mat , int n ) { int finalLeft = 0 , finalRight = 0 , finalTop = 0 , finalBottom = 0 ; int maxArea = 0 , len ; finish = 0 ; start = 0 ; int [ ] temp = new int [ n ] ; for ( int left = 0 ; left < n ; left ++ ) { Arrays . fill ( temp , 0 ) ; 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 ) ; 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 ) ; } } } System . out . print ( " ( Top , ▁ Left ) : ▁ ( " + finalTop + " , ▁ " + finalLeft + ")NEW_LINE"); System . out . print ( " ( Bottom , ▁ Right ) : ▁ ( " + finalBottom + " , ▁ " + finalRight + ")NEW_LINE"); System . out . print ( " Maximum ▁ area : ▁ " + maxArea ) ; } public static void main ( String [ ] args ) { int [ ] [ ] mat = new int [ ] [ ] { { 1 , 0 , 0 , 1 } , { 0 , 1 , 1 , 1 } , { 1 , 0 , 0 , 0 } , { 0 , 1 , 0 , 1 } } ; int n = 4 ; largestSubmatrix ( mat , n ) ; } }