Queries to find the maximum array element after removing elements from a given range | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMaximum ( int arr [ ] , int N , int Q , int queries [ ] [ 2 ] ) { int prefix_max [ N + 1 ] = { 0 } ; int suffix_max [ N + 1 ] = { 0 } ; prefix_max [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { prefix_max [ i ] = 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 ] = 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 ) ) cout << "0 STRNEWLINE " ; else if ( l == 0 ) cout << suffix_max [ r + 1 ] << " STRNEWLINE " ; else if ( r == ( N - 1 ) ) cout << prefix_max [ l - 1 ] << " STRNEWLINE " ; else cout << max ( prefix_max [ l - 1 ] , suffix_max [ r + 1 ] ) << " STRNEWLINE " ; } } int main ( ) { int arr [ ] = { 5 , 6 , 8 , 10 , 15 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int queries [ ] [ 2 ] = { { 0 , 1 } , { 0 , 2 } , { 1 , 4 } } ; int Q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; findMaximum ( arr , N , Q , queries ) ; return 0 ; }