Maximum product of indexes of next greater on left and right | Java 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 ; Driver code
import java . io . * ; import java . util . * ; class GFG { static int MAX = 1000 ; static int [ ] nextGreaterInLeft ( int [ ] a , int n ) { int [ ] left_index = new int [ MAX ] ; Stack < Integer > s = new Stack < Integer > ( ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( s . size ( ) != 0 && a [ i ] > a [ s . peek ( ) - 1 ] ) { int r = s . peek ( ) ; s . pop ( ) ; left_index [ r - 1 ] = i + 1 ; } s . push ( i + 1 ) ; } return left_index ; } static int [ ] nextGreaterInRight ( int [ ] a , int n ) { int [ ] right_index = new int [ MAX ] ; Stack < Integer > s = new Stack < Integer > ( ) ; for ( int i = 0 ; i < n ; ++ i ) { while ( s . size ( ) != 0 && a [ i ] > a [ s . peek ( ) - 1 ] ) { int r = s . peek ( ) ; s . pop ( ) ; right_index [ r - 1 ] = i + 1 ; } s . push ( i + 1 ) ; } return right_index ; } static int LRProduct ( int [ ] arr , int n ) { int [ ] left = nextGreaterInLeft ( arr , n ) ; int [ ] right = nextGreaterInRight ( arr , n ) ; int ans = - 1 ; for ( int i = 1 ; i <= n ; i ++ ) { ans = Math . max ( ans , left [ i ] * right [ i ] ) ; } return ans ; } public static void main ( String args [ ] ) { int [ ] arr = new int [ ] { 5 , 4 , 3 , 4 , 5 } ; int n = arr . length ; System . out . print ( LRProduct ( arr , n ) ) ; } }