Maximum size rectangle binary sub | Java program to find largest rectangle with all 1 s in a binary matrix ; Finds the maximum area under the histogram represented by histogram . See below article for ; Create an empty stack . The stack holds indexes of hist [ ] array / The bars stored in stack are always in increasing order of their heights . ; Top of stack ; Initialize max area in current ; row ( or histogram ) Initialize area with current top ; Run through all bars of given histogram ( or row ) ; If this bar is higher than the bar on top stack , push it to stack ; If this bar is lower than top of stack , then calculate area of rectangle with stack top as the smallest ( or minimum height ) bar . ' i ' is ' right ▁ index ' for the top and element before top in stack is ' left ▁ index ' ; Now pop the remaining bars from stack and calculate area with every popped bar as the smallest bar ; Returns area of the largest rectangle with all 1 s in A [ ] [ ] ; Calculate area for first row and initialize it as result ; iterate over row to find maximum rectangular area considering each row as histogram ; if A [ i ] [ j ] is 1 then add A [ i - 1 ] [ j ] ; Update result if area with current row ( as last row of rectangle ) is more ; Driver code
import java . io . * ; import java . util . * ; class GFG { static int maxHist ( int R , int C , int row [ ] ) { Stack < Integer > result = new Stack < Integer > ( ) ; int top_val ; int max_area = 0 ; int area = 0 ; int i = 0 ; while ( i < C ) { if ( result . empty ( ) || row [ result . peek ( ) ] <= row [ i ] ) result . push ( i ++ ) ; else { top_val = row [ result . peek ( ) ] ; result . pop ( ) ; area = top_val * i ; if ( ! result . empty ( ) ) area = top_val * ( i - result . peek ( ) - 1 ) ; max_area = Math . max ( area , max_area ) ; } } while ( ! result . empty ( ) ) { top_val = row [ result . peek ( ) ] ; result . pop ( ) ; area = top_val * i ; if ( ! result . empty ( ) ) area = top_val * ( i - result . peek ( ) - 1 ) ; max_area = Math . max ( area , max_area ) ; } return max_area ; } static int maxRectangle ( int R , int C , int A [ ] [ ] ) { int result = maxHist ( R , C , A [ 0 ] ) ; for ( int i = 1 ; i < R ; i ++ ) { for ( int j = 0 ; j < C ; j ++ ) if ( A [ i ] [ j ] == 1 ) A [ i ] [ j ] += A [ i - 1 ] [ j ] ; result = Math . max ( result , maxHist ( R , C , A [ i ] ) ) ; } return result ; } public static void main ( String [ ] args ) { int R = 4 ; int C = 4 ; int A [ ] [ ] = { { 0 , 1 , 1 , 0 } , { 1 , 1 , 1 , 1 } , { 1 , 1 , 1 , 1 } , { 1 , 1 , 0 , 0 } , } ; System . out . print ( " Area ▁ of ▁ maximum ▁ rectangle ▁ is ▁ " + maxRectangle ( R , C , A ) ) ; } }