Maximum range length such that A [ i ] is maximum in given range for all i from [ 1 , N ] | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void MaxRange ( vector < int > A , int n ) { vector < int > left ( n ) , right ( n ) ; stack < pair < int , int > > s ; s . push ( { INT_MAX , -1 } ) ; for ( int i = 0 ; i < n ; i ++ ) { while ( s . top ( ) . first < A [ i ] ) s . pop ( ) ; left [ i ] = s . top ( ) . second ; s . push ( { A [ i ] , i } ) ; } while ( ! s . empty ( ) ) s . pop ( ) ; s . push ( make_pair ( INT_MAX , n ) ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( s . top ( ) . first < A [ i ] ) s . pop ( ) ; right [ i ] = s . top ( ) . second ; s . push ( { A [ i ] , i } ) ; } for ( int i = 0 ; i < n ; i ++ ) { cout << left [ i ] + 1 << ' ▁ ' << right [ i ] - 1 << " STRNEWLINE " ; } } int main ( ) { vector < int > arr { 1 , 3 , 2 } ; int n = arr . size ( ) ; MaxRange ( arr , n ) ; return 0 ; }