Queries to find the maximum and minimum array elements excluding elements from a given range | C ++ program for the above approach ; Function to find the maximum and minimum array elements up to the i - th index ; Traverse the array ; Compare current value with maximum and minimum values up to previous index ; Function to find the maximum and minimum array elements from i - th index ; Traverse the array in reverse ; Compare current value with maximum and minimum values in the next index ; Function to find the maximum and minimum array elements for each query ; If no index remains after excluding the elements in a given range ; Find maximum and minimum from from the range [ R + 1 , N - 1 ] ; Find maximum and minimum from from the range [ 0 , N - 1 ] ; Find maximum and minimum values from the ranges [ 0 , L - 1 ] and [ R + 1 , N - 1 ] ; Print the maximum and minimum value ; Function to perform queries to find the minimum and maximum array elements excluding elements from a given range ; Size of the array ; Size of query array ; prefix [ i ] [ 0 ] : Stores the maximum prefix [ i ] [ 1 ] : Stores the minimum value ; suffix [ i ] [ 0 ] : Stores the maximum suffix [ i ] [ 1 ] : Stores the minimum value ; Function calls to store maximum and minimum values for respective ranges ; Driver Code ; Given array
#include <bits/stdc++.h> NEW_LINE using namespace std ; void prefixArr ( int arr [ ] , int prefix [ ] [ 2 ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) { if ( i == 0 ) { prefix [ i ] [ 0 ] = arr [ i ] ; prefix [ i ] [ 1 ] = arr [ i ] ; } else { prefix [ i ] [ 0 ] = max ( prefix [ i - 1 ] [ 0 ] , arr [ i ] ) ; prefix [ i ] [ 1 ] = min ( prefix [ i - 1 ] [ 1 ] , arr [ i ] ) ; } } } void suffixArr ( int arr [ ] , int suffix [ ] [ 2 ] , int N ) { for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( i == N - 1 ) { suffix [ i ] [ 0 ] = arr [ i ] ; suffix [ i ] [ 1 ] = arr [ i ] ; } else { suffix [ i ] [ 0 ] = max ( suffix [ i + 1 ] [ 0 ] , arr [ i ] ) ; suffix [ i ] [ 1 ] = min ( suffix [ i + 1 ] [ 1 ] , arr [ i ] ) ; } } } void maxAndmin ( int prefix [ ] [ 2 ] , int suffix [ ] [ 2 ] , int N , int L , int R ) { int maximum , minimum ; if ( L == 0 && R == N - 1 ) { cout << " No ▁ maximum ▁ and ▁ minimum ▁ value " << endl ; return ; } else if ( L == 0 ) { maximum = suffix [ R + 1 ] [ 0 ] ; minimum = suffix [ R + 1 ] [ 1 ] ; } else if ( R == N - 1 ) { maximum = prefix [ L - 1 ] [ 0 ] ; minimum = prefix [ R - 1 ] [ 1 ] ; } else { maximum = max ( prefix [ L - 1 ] [ 0 ] , suffix [ R + 1 ] [ 0 ] ) ; minimum = min ( prefix [ L - 1 ] [ 1 ] , suffix [ R + 1 ] [ 1 ] ) ; } cout << maximum << " ▁ " << minimum << endl ; } void MinMaxQueries ( int a [ ] , int Q [ ] [ ] ) { int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; int prefix [ N ] [ 2 ] ; int suffix [ N ] [ 2 ] ; prefixArr ( arr , prefix , N ) ; suffixArr ( arr , suffix , N ) ; for ( int i = 0 ; i < q ; i ++ ) { int L = queries [ i ] [ 0 ] ; int R = queries [ i ] [ 1 ] ; maxAndmin ( prefix , suffix , N , L , R ) ; } } int main ( ) { int arr [ ] = { 2 , 3 , 1 , 8 , 3 , 5 , 7 , 4 } ; int queries [ ] [ 2 ] = { { 4 , 6 } , { 0 , 4 } , { 3 , 7 } , { 2 , 5 } } ; MinMaxQueries ( arr , Q ) ; return 0 ; }