Maximum size rectangle binary sub | C # 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 details . https : www . geeksforgeeks . org / largest - rectangle - under - histogram / ; 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
using System ; using System . Collections . Generic ; class GFG { public static int maxHist ( int R , int C , int [ ] row ) { Stack < int > result = new Stack < int > ( ) ; int top_val ; int max_area = 0 ; int area = 0 ; int i = 0 ; while ( i < C ) { if ( result . Count == 0 || row [ result . Peek ( ) ] <= row [ i ] ) { result . Push ( i ++ ) ; } else { top_val = row [ result . Peek ( ) ] ; result . Pop ( ) ; area = top_val * i ; if ( result . Count > 0 ) { area = top_val * ( i - result . Peek ( ) - 1 ) ; } max_area = Math . Max ( area , max_area ) ; } } while ( result . Count > 0 ) { top_val = row [ result . Peek ( ) ] ; result . Pop ( ) ; area = top_val * i ; if ( result . Count > 0 ) { area = top_val * ( i - result . Peek ( ) - 1 ) ; } max_area = Math . Max ( area , max_area ) ; } return max_area ; } public 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 = new int [ ] [ ] { new int [ ] { 0 , 1 , 1 , 0 } , new int [ ] { 1 , 1 , 1 , 1 } , new int [ ] { 1 , 1 , 1 , 1 } , new int [ ] { 1 , 1 , 0 , 0 } } ; Console . Write ( " Area ▁ of ▁ maximum ▁ rectangle ▁ is ▁ " + maxRectangle ( R , C , A ) ) ; } }