Maximum product of indexes of next greater on left and right | C ++ program to find the max LRproduct [ i ] among all i ; function to find just next greater element in left side ; checking if current element is greater than top ; on index of top store the current element index which is just greater than top element ; else push the current element in stack ; function to find just next greater element in right side ; checking if current element is greater than top ; on index of top store the current element index which is just greater than top element stored index should be start with 1 ; else push the current element in stack ; Function to find maximum LR product ; for each element storing the index of just greater element in left side ; for each element storing the index of just greater element in right side ; finding the max index product ; Drivers code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000 NEW_LINE vector < int > nextGreaterInLeft ( int a [ ] , int n ) { vector < int > left_index ( MAX , 0 ) ; stack < int > s ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( ! s . empty ( ) && a [ i ] > a [ s . top ( ) - 1 ] ) { int r = s . top ( ) ; s . pop ( ) ; left_index [ r - 1 ] = i + 1 ; } s . push ( i + 1 ) ; } return left_index ; } vector < int > nextGreaterInRight ( int a [ ] , int n ) { vector < int > right_index ( MAX , 0 ) ; stack < int > s ; for ( int i = 0 ; i < n ; ++ i ) { while ( ! s . empty ( ) && a [ i ] > a [ s . top ( ) - 1 ] ) { int r = s . top ( ) ; s . pop ( ) ; right_index [ r - 1 ] = i + 1 ; } s . push ( i + 1 ) ; } return right_index ; } int LRProduct ( int arr [ ] , int n ) { vector < int > left = nextGreaterInLeft ( arr , n ) ; vector < int > right = nextGreaterInRight ( arr , n ) ; int ans = -1 ; for ( int i = 1 ; i <= n ; i ++ ) { ans = max ( ans , left [ i ] * right [ i ] ) ; } return ans ; } int main ( ) { int arr [ ] = { 5 , 4 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 1 ] ) ; cout << LRProduct ( arr , n ) ; return 0 ; }