Find Maximum Index Product

                            Solution in C :

In   C++  :








#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int inp[100010];
int sta[100010][2];
int lef[100010];
int rig[100010];
int n;

void find(int *arr, int st, int ed, int d, int *out) {
    int top = 1;
    sta[0][0] = 2000000000;
    sta[0][1] = 0;
    for (int i=st; i!=ed; i+=d) {
        while (sta[top-1][0] <= arr[i]) top--;
        out[i] = sta[top-1][1];
        sta[top][0] = arr[i];
        sta[top++][1] = i+1;
    }
    return;
}
int main() {
  
    scanf("%d", &n);
    for (int i=0; i<n; i++)scanf("%d", &inp[i]);
    find(inp, 0, n, 1, lef);
    find(inp, n-1, -1, -1, rig);
    long long ans = 0;
    for (int i=0; i<n; i++) {
        if ((long long)lef[i] * rig[i] > ans) ans = (long long)lef[i] * rig[i];
    }
    cout << ans << endl;
    return 0;
}










In    Java  :








import java.awt.Point;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Solution {
public static void main(String[] args) throws IOException,
NumberFormatException {
BufferedReader br = new BufferedReader(
    new InputStreamReader(System.in));
BufferedOutputStream bos = 
new BufferedOutputStream(System.out);
byte[] eolb = System.getProperty(
    "line.separator").getBytes();

int n = Integer.parseInt(br.readLine().trim());
String[] values = br.readLine().trim().split(" ");
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(values[i]);
}

long[] leftArr = new long[n];
ArrayList<Point> states = new ArrayList<Point>();
states.add(new Point((int) arr[0], 1));
for (int i = 1; i < n; i++) {
for (int j = states.size() - 1; j >= 0; j--) {
if (states.get(j).getX() > arr[i]) {
leftArr[i] = (int) states.get(j).getY();
states.add(new Point((int) arr[i], i + 1));
break;
} else {
states.remove(j);
if (states.size() == 0) {
states.add(new Point((int) arr[i], i + 1));
break;
}
}
}
}
states.clear();

long[] rightArr = new long[n];
states.add(new Point((int) arr[n - 1], n));
for (int i = n - 2; i >= 0; i--) {
for (int j = states.size() - 1; j >= 0; j--) {
if (states.get(j).getX() > arr[i]) {
rightArr[i] = (int) states.get(j).getY();
states.add(new Point((int) arr[i], i + 1));
break;
} else {
states.remove(j);
if (states.size() == 0) {
states.add(new Point((int) arr[i], i + 1));
break;
}
}
}
}

long ans = -1;
for (int i = 0; i < n; i++) {
ans = Math.max(ans,
 (long) leftArr[i] * rightArr[i]);
}
bos.write(String.valueOf(ans).getBytes());
bos.write(eolb);
bos.flush();

}
}










In   C  :







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

int main() {

  
    long int n, left=0, right=0, i, j, a[100000], out, max=0;
    
    scanf("%ld", &n);
    for(i=0;i<n;i++)
        {
        scanf("%ld", &a[i]);
    }
    for(i=n-1;i>=1;i--)
        {
    /*    for(j=i-1;j>=0;j--)
            {
            if(a[j]>a[i])
                {
                left=j+1;
                break;
            }
        }
        for(j=i+1;j<=n-1;j++)
            {
            if(a[j]>a[i])
                {
                right=j+1;
                break;
            }
        }*/
        if(a[i]<a[i+1]&&a[i]<a[i-1])
            {
            max=i*(i+2);
            break;
        }
        
        
        /*out=left*right;
        if(out>max)
            max=out;
        left=0;
        right=0;*/
        
    }
    printf("%ld", max);
    return 0;
}










In   Python3  :







def lefts(L):
    left = [];
    maxes = [];
    for i in range(len(L)):
        while maxes and L[maxes[-1]] <= L[i]:
            maxes.pop();
        if not maxes: left.append(-1);
        else: left.append(maxes[-1]);
        maxes.append(i); #maxes = [i];
    return left;

def rights(L):
    right = [];
    maxes = [];
    for i in range(len(L)-1, -1, -1):
        while maxes and L[maxes[-1]] <= L[i]:
            maxes.pop();
        if not maxes: right.append(-1);
        else: right.append(maxes[-1]);
        maxes.append(i); #maxes = [i];
    right.reverse();
    return right;

def indexProduct(L):
    left = lefts(L);
    right = rights(L);
    products = ((left[i] + 1) * (right[i] + 1) for i in range(len(L)));
    return max(products);


if __name__ == "__main__":
    input();
    L = [int(n) for n in input().split()];
    print(indexProduct(L));