Maximum size rectangle binary sub | Finds the maximum area under the histogram represented by histogram . See below article for details . ; 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
class Solution ( ) : NEW_LINE INDENT def maxHist ( self , row ) : NEW_LINE INDENT result = [ ] NEW_LINE top_val = 0 NEW_LINE max_area = 0 NEW_LINE area = 0 NEW_LINE i = 0 NEW_LINE while ( i < len ( row ) ) : NEW_LINE INDENT if ( len ( result ) == 0 ) or ( row [ result [ - 1 ] ] <= row [ i ] ) : NEW_LINE INDENT result . append ( i ) NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT top_val = row [ result . pop ( ) ] NEW_LINE area = top_val * i NEW_LINE if ( len ( result ) ) : NEW_LINE INDENT area = top_val * ( i - result [ - 1 ] - 1 ) NEW_LINE DEDENT max_area = max ( area , max_area ) NEW_LINE DEDENT DEDENT while ( len ( result ) ) : NEW_LINE INDENT top_val = row [ result . pop ( ) ] NEW_LINE area = top_val * i NEW_LINE if ( len ( result ) ) : NEW_LINE INDENT area = top_val * ( i - result [ - 1 ] - 1 ) NEW_LINE DEDENT max_area = max ( area , max_area ) NEW_LINE DEDENT return max_area NEW_LINE DEDENT def maxRectangle ( self , A ) : NEW_LINE INDENT result = self . maxHist ( A [ 0 ] ) NEW_LINE for i in range ( 1 , len ( A ) ) : NEW_LINE INDENT for j in range ( len ( A [ i ] ) ) : NEW_LINE INDENT if ( A [ i ] [ j ] ) : NEW_LINE INDENT A [ i ] [ j ] += A [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT result = max ( result , self . maxHist ( A [ i ] ) ) NEW_LINE DEDENT return result NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ [ 0 , 1 , 1 , 0 ] , [ 1 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 ] , [ 1 , 1 , 0 , 0 ] ] NEW_LINE ans = Solution ( ) NEW_LINE print ( " Area ▁ of ▁ maximum ▁ rectangle ▁ is " , ans . maxRectangle ( A ) ) NEW_LINE DEDENT