Queries to find the maximum array element after removing elements from a given range | Java program for the above approach ; 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
class GFG { static void findMaximum ( int arr [ ] , int N , int Q , int queries [ ] [ ] ) { int prefix_max [ ] = new int [ N + 1 ] ; int suffix_max [ ] = new int [ N + 1 ] ; prefix_max [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { prefix_max [ i ] = Math . max ( prefix_max [ i - 1 ] , arr [ i ] ) ; } suffix_max [ N - 1 ] = arr [ N - 1 ] ; for ( int i = N - 2 ; i >= 0 ; i -- ) { suffix_max [ i ] = Math . max ( suffix_max [ i + 1 ] , arr [ i ] ) ; } for ( int i = 0 ; i < Q ; i ++ ) { int l = queries [ i ] [ 0 ] ; int r = queries [ i ] [ 1 ] ; if ( l == 0 && r == ( N - 1 ) ) System . out . print ( "0NEW_LINE"); else if ( l == 0 ) System . out . print ( suffix_max [ r + 1 ] + "NEW_LINE"); else if ( r == ( N - 1 ) ) System . out . print ( prefix_max [ l - 1 ] + "NEW_LINE"); else System . out . print ( Math . max ( prefix_max [ l - 1 ] , suffix_max [ r + 1 ] ) + "NEW_LINE"); } } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 6 , 8 , 10 , 15 } ; int N = arr . length ; int queries [ ] [ ] = { { 0 , 1 } , { 0 , 2 } , { 1 , 4 } } ; int Q = queries . length ; findMaximum ( arr , N , Q , queries ) ; } }