Find Maximum Index Product-Hackerrank - Shanmugaguru

https://www.hackerrank.com/challenges/find-maximum-index-product/problem

You are given a list of  numbers . For each element at position  (), we define  and  as:
 = closest index j such that j < i and . If no such j exists then  = 0.
 = closest index k such that k > i and . If no such k exists then  = 0.

We define  =  * . You need to find out the maximum  among all i.

Input Format

The first line contains an integer , the number of integers. The next line contains the  integers describing the list a[1..N].

Constraints

Output Format

Output the maximum  among all indices from  to .

Sample Input

5
5 4 3 4 5

Sample Output

8

Explanation

We can compute the following:

The largest of these is 8, so it is the answer.

int leftprod[100005]; int rightprod[100005]; int arr[100005]; 
int main()
{
    stack <PII> first, second;
    int a; cin >> a;
    for (int g=1;g<=a; g++) cin >> arr[g]; 
    for (int g=1;g<=a; g++)
    {
        while (!first.empty() && first.top().first<=arr[g]) first.pop();
        if (first.empty()){first.push(PII(arr[g], g)); continue;}
        leftprod[g]=first.top().second; 
        first.push(PII(arr[g], g)); 
    }
    for (int g=a; g>=1; g--)
    {
        while (!second.empty() && second.top().first<=arr[g]) second.pop();
        if (second.empty()){second.push(PII(arr[g], g)); continue;}
        rightprod[g]=second.top().second; 
        second.push(PII(arr[g], g)); 
    }long long ans=0; 
    for (int g=1; g<=a; g++)
    {
        long long t=1LL*leftprod[g]*rightprod[g];
        if (t>ans) ans=t; 
    }
    cout << ans; return 0; 
}

Find Maximum Index Product-Hackerrank - Shanmugaguru
     Given an array of elements,the problem asks us to find two indices 'l' & 'r' for every indices 'I' such that a[l]>a[i] and a[r]>a[i] such that 'l' & 'r' are as close to 'I' as possible and l<I and r>i. And if no such index is found the value for that index is assumed to be "0" else the value is the product of l and r.
Ordered Stack:
https://codepair.hackerrank.com/paper/OzKyiHeW?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
https://www.hackerrank.com/challenges/find-maximum-index-product/editorial
        Long[] left = new Long[N];
        Stack<Integer> leftStack = new Stack<Integer>();
        leftStack.push(0);
        left[0] = new Long(0);
        for (int i = 1; i < N; i++) {
            while (!leftStack.isEmpty() && numbers[leftStack.peek()] <= numbers[i]) {
                leftStack.pop();
            }
            if (leftStack.isEmpty()) {
                left[i] = new Long(0);
            } else {
                left[i] = new Long(leftStack.peek()+1);
            }
            leftStack.push(i);
        }
     
        Long[] right = new Long[N];
        Stack<Integer> rightStack = new Stack<Integer>();
        rightStack.push(N-1);
        right[N-1] = new Long(0);
        for (int i = N-2; i >= 0; i--) {
            while (!rightStack.isEmpty() && numbers[rightStack.peek()] <= numbers[i]) {
                rightStack.pop();
            }
            if (rightStack.isEmpty()) {
                right[i] = new Long(0);
            } else {
                right[i] = new Long(rightStack.peek()+1);
            }
            rightStack.push(i);
        }
     
        long max = 0;
        for (int i = 0; i < N; i++) {
            if (left[i] * right[i] > max) {
                max = left[i] * right[i];
            }
        }
https://github.com/charles-wangkai/hackerrank/blob/master/find-maximum-index-product/Solution.java

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();

    int[] a = new int[N];

    for (int i = 0; i < a.length; i++) {

      a[i] = sc.nextInt();

    }

    int[] lefts = buildClosests(a, IntStream.range(0, a.length).toArray());

    int[] rights = buildClosests(a, IntStream.range(0, a.length).map(i -> a.length - 1 - i).toArray());

    long maxProduct = Long.MIN_VALUE;

    for (int i = 0; i < lefts.length; i++) {

      maxProduct = Math.max(maxProduct, (long) lefts[i] * rights[i]);

    }

    System.out.println(maxProduct);

    sc.close();

  }

  static int[] buildClosests(int[] a, int[] indices) {

    int[] closests = new int[a.length];

    Stack<Integer> indexStack = new Stack<Integer>();

    for (int index : indices) {

      while (!indexStack.empty() && a[index] >= a[indexStack.peek()]) {

        indexStack.pop();

      }

      closests[index] = indexStack.empty() ? 0 : (indexStack.peek() + 1);

      indexStack.push(index);

    }

    return closests;

  }

https://github.com/algorhythms/HackerRankAlgorithms/blob/master/Find%20Maximum%20Index%20Product.py
What's the time complexity?
    def solve(self, cipher):
        A = cipher
        L = [-1 for _ in A]
        for i in xrange(1, len(A)):
            idx = i-1
            while idx!=-1:
                if A[idx]>A[i]:
                    L[i] = idx
                    break
                idx = L[idx]

        R = [-1 for _ in A]
        for i in xrange(len(A)-2, -1, -1):
            idx = i+1
            while idx!=-1:
                if A[idx]>A[i]:
                    R[i] = idx
                    break
                idx = R[idx]

        maxa = -1
        for i in xrange(len(A)):
            left = L[i]+1
            right = R[i]+1
            maxa = max(maxa, left*right)

        return maxa
Brute Force:
https://codeifyoucansolve.wordpress.com/2015/03/01/find-maximum-index-product/

1. for(i=1;i<(n-1);i++)
2. {
3. l=i-1;
4. while(l>=0)
5. {
6. if(arr[l]>arr[i])
7. break;
8. l--;
9. }
10. if(arr[l]>arr[i])
11. l = l+1;
12. else
13. l=0;
14. r=i+1;
15. while(r<n)
16. {
17. if(arr[r]>arr[i])
18. break;
19. r++;
20. }
21. if(r==n)
22. r=0;
23. else
24. r=r+1;
25. max_p = l*r;
26. if(max_p>max)
27. max=max_p;
28. }

Read full article from Find Maximum Index Product-Hackerrank - Shanmugaguru