Maximum Index Geeks Solution

Maximum Index Geeks Solution

  February 12, 2018    

---

Problem:
Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j]

Idea is to use stack and push in decresing order.
Pop index until stack element is less than current element


import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
public static int maxIndexDiff(int arr[],int n)
{
Stack<Integer> stk=new Stack<Integer>();
for(int i=0;i<n;++i)
{
if(stk.isEmpty() || arr[i]<arr[stk.peek()])
stk.push(i);
}
int res=-1;
for(int i=n-1;i>=0;--i)
{
while(!stk.isEmpty() && arr[i]>=arr[stk.peek()])
res=Math.max(res,i-stk.pop());
//remove all values which have processed i.e. index that has been used
while(!stk.isEmpty() && i<stk.peek())
stk.pop();
}
return res;
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(maxIndexDiff(arr,n));
}
}
}