Maximum range length such that A [ i ] is maximum in given range for all i from [ 1 , N ] | Python 3 program for the above approach ; Function to find maximum range for each i such that arr [ i ] is max in range ; Vector to store the left and right index for each i such that left [ i ] > arr [ i ] and right [ i ] > arr [ i ] ; Traverse the array ; While s . top ( ) . first < a [ i ] remove the top element from the stack ; Modify left [ i ] ; Clear the stack ; Traverse the array to find right [ i ] for each i ; While s . top ( ) . first < a [ i ] remove the top element from the stack ; Modify right [ i ] ; Print the value range for each i ; Driver Code ; Given Input ; Function Call
import sys NEW_LINE def MaxRange ( A , n ) : NEW_LINE INDENT left = [ 0 ] * n NEW_LINE right = [ 0 ] * n NEW_LINE s = [ ] NEW_LINE s . append ( ( sys . maxsize , - 1 ) ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT while ( s [ - 1 ] [ 0 ] < A [ i ] ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT left [ i ] = s [ - 1 ] [ 1 ] NEW_LINE s . append ( ( A [ i ] , i ) ) NEW_LINE DEDENT while ( len ( s ) != 0 ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT s . append ( ( sys . maxsize , n ) ) NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT while ( s [ - 1 ] [ 0 ] < A [ i ] ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT right [ i ] = s [ - 1 ] [ 1 ] NEW_LINE s . append ( ( A [ i ] , i ) ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT print ( left [ i ] + 1 , ' ▁ ' , right [ i ] - 1 ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 3 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE MaxRange ( arr , n ) NEW_LINE DEDENT