Queries to find the maximum array element after removing elements from a given range | Function to find the maximum element after removing elements in range [ l , r ] ; Store prefix maximum element ; Store suffix maximum element ; Prefix max till first index is first index itself ; Traverse the array to fill prefix max array ; Store maximum till index i ; Suffix max till last index is last index itself ; Traverse the array to fill suffix max array ; Store maximum till index i ; Traverse all queries ; Store the starting and the ending index of the query ; Edge Cases ; Otherwise ; Driver Code
def findMaximum ( arr , N , Q , queries ) : NEW_LINE INDENT prefix_max = [ 0 ] * ( N + 1 ) NEW_LINE suffix_max = [ 0 ] * ( N + 1 ) NEW_LINE prefix_max [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT prefix_max [ i ] = max ( prefix_max [ i - 1 ] , arr [ i ] ) NEW_LINE DEDENT suffix_max [ N - 1 ] = arr [ N - 1 ] NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT suffix_max [ i ] = max ( suffix_max [ i + 1 ] , arr [ i ] ) NEW_LINE DEDENT for i in range ( Q ) : NEW_LINE INDENT l = queries [ i ] [ 0 ] NEW_LINE r = queries [ i ] [ 1 ] NEW_LINE if ( l == 0 and r == ( N - 1 ) ) : NEW_LINE INDENT print ( "0" ) NEW_LINE DEDENT elif ( l == 0 ) : NEW_LINE INDENT print ( suffix_max [ r + 1 ] ) NEW_LINE DEDENT elif ( r == ( N - 1 ) ) : NEW_LINE INDENT print ( prefix_max [ l - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( max ( prefix_max [ l - 1 ] , suffix_max [ r + 1 ] ) ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 5 , 6 , 8 , 10 , 15 ] NEW_LINE N = len ( arr ) NEW_LINE queries = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 1 , 4 ] ] NEW_LINE Q = len ( queries ) NEW_LINE findMaximum ( arr , N , Q , queries ) NEW_LINE DEDENT