Find Maximum Index Product

You are given a list of n numbers a1,a2,…,an. For each i (1≤i≤n), define LEFT(i) to be the nearest index j before i such that aj>ai. Note that if j does not exist, we should consider LEFT(i) to be 0. Similarly, define RIGHT(i) to be the nearest index j after i such that aj>ai. Note that if j does not exist, we should consider RIGHT(i) to be 0.

Define INDEXPRODUCT(i) as the product of LEFT(i) and RIGHT(i). Find the maximum INDEXPRODUCT(i) among all 1≤i≤n.

Input Format

The first line contains an integer n, the number of integers. The next line contains the N integers.

Constraints:

1≤N≤105

Each of the N integers will range from 0 to 109

Output Format

Output the maximum INDEXPRODUCT among all indices from 1 to N.

Sample Input

5
5 4 3 4 5

Sample Output

8

Explanation

We can compute the following:

INDEXPRODUCT(1)=0
INDEXPRODUCT(2)=1×5=5
INDEXPRODUCT(3)=2×4=8
INDEXPRODUCT(4)=1×5=5
INDEXPRODUCT(5)=0

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

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
  long int n,arr[100000],i,l,r;
    long long int max=0,max_p=0;
    scanf("%ld",&n);
    for(i=0;i<n;i++)
        {
        scanf("%ld",&arr[i]);
    }
    for(i=1;i<(n-1);i++)
        {
        l=i-1;
        while(l>=0)
            {
            if(arr[l]>arr[i])
                break;
            l--;
        }
        if(arr[l]>arr[i])
            l = l+1;
        else
            l=0;
        r=i+1;
        while(r<n)
            {
            if(arr[r]>arr[i])
                break;
            r++;
        }
        if(r==n)
            r=0;
        else
            r=r+1;
        max_p = l*r;
        if(max_p>max)
            max=max_p;
    }
    printf("%lld",max);
    return 0;
}

Compile & Run : https://ideone.com/so4aiz