Algorithm

Problem Name: Data Structures - Find Maximum Index Product

In this HackerRank in Data Structures - Find Maximum Index Product solutions

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

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

int findLeft(const int value,const int start,const int end,const int v[]) {
int result=start;
while(v[result] < =value && result>end) result--;
return result;
}
int findRight(const int value,const int start,const int v[]) {
int result=start;
while(v[result] < =value) result++;
return result;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n; scanf("%d",&n);
if(n<3) {
// no need to compute anything, result is zero
printf("0\n");
} else {
int v[n+1],l[n+1],leftMax=0;
for(int i=0;i < n;) {
scanf("%d ",&v[++i]>;
l[i]=leftMax; if(v[i]>leftMax) leftMax=v[i];
}
long int maxProd=0;    // the current max product
long int rightPos,current;    // actual start from right, current position
int rightMax=v[n];        // actual value of start right
current=n-1;
while(current>2 && v[current]>=rightMax) {
rightMax=v[current--];
}
rightPos=current+1;
if(current>=2) {
if(v[current]<l[current]) {
long int leftPos=findLeft(v[current],current-1,leftPos,v>;
long int prod=leftPos*rightPos;
if(prod>maxProd) maxProd=prod;
}
current--;
while(current>1 && (current-1)*rightPos>maxProd) {
int value=v[current];
if(value>=rightMax) {
// no right
rightMax=value; rightPos=current;
} else {
if(value<l[current]) {
long int right=findRight(value,current+1,v);
long int leftPos=findLeft(value,current-1,leftPos,v);
#ifdef DEBUG
printf("current=%d,left=%d,right=%d\n",current,leftPos,right>;
#endif
long int prod=leftPos*right;
if(prod>maxProd) maxProd=prod;
}
}
current--;
}
}
printf("%ld\n",maxProd);
}
return 0;
}
``````
Copy The Code &

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

using namespace std;

typedef long long     LL;
typedef pair < int,int> pii;

double PI  = acos(-1);
double EPS = 1e-7;
int INF    = 1000000000;
LL INFLL   = 1000000000000000000LL;

#define fi            first
#define se            second
#define mp            make_pair
#define pb            push_back

#define input(in)     freopen(in,"r",stdin)
#define output(out)   freopen(out,"w",stdout)

#define MIN(a, b)     (a) = min((a), (b))
#define MAX(a, b)     (a) = max((a), (b))

#define RESET(a, b)   memset(a,b,sizeof(a))
#define ALL(a)        (a).begin(), (a).end()
#define SIZE(a)       (int)a.size()
#define SORT(a)       sort(ALL(a))
#define UNIQUE(a)     (a).erase( unique( ALL(a) ), (a).end() )
#define FOR(a, b, c)  for (int (a)=(b); (a) < =(c); (a)++)
#define FORD(a, b, c) for (int (a)=(b); (a)>=(c); (a)--)
#define FORIT(a, b)   for (__typeof((b).begin()) a=(b).begin(); a!=(b).end(); a++)

int mx[8] = {-1,1,0,0,-1,-1,1,1};
int my[8] = {0,0,-1,1,-1,1,-1,1};

// ----- //

int x[100005];
int fl[100005];
int fr[100005];

int main()
{
int n;
scanf("%d",&n);
FOR(a,1,n)
{
scanf("%d",&x[a]);
}
x[0] = INF+1;
vector<int> stk;
stk.pb(0);
FOR(a,1,n) {
while(x[stk.back()]  < = x[a]) {
stk.pop_back();
}
fl[a] = stk.back();
stk.pb(a);
}
stk.clear();
stk.pb(0);
FORD(a,n,1) {
while(x[stk.back()]  < = x[a]) {
stk.pop_back();
}
fr[a] = stk.back();
stk.pb(a);
}
long long ans = 0;
FOR(a,1,n) {
MAX(ans,(LL)fl[a]*fr[a]);
}
cout << ans << endl;
}
``````
Copy The Code &

#3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int[] left = GetBounds(vals, -1);
int[] right = GetBounds(vals, 1);
long max = 0, prod;
for (int i = 0; i  <  vals.length; i++) {
prod = (long)left[i] * right[i];
if (prod > max) {
max = prod;
}
}
System.out.println(max);
}

public static int[] Read(Scanner s) {
int numVals = s.nextInt();
int[] vals = new int[numVals];
for (int i = 0; i  <  numVals; i++) {
vals[i] = s.nextInt();
}
return vals;
}

public static int[] GetBounds(int[] vals, int dir) {
int start, end, inc;
int[] bounds = new int[vals.length];
if (dir == 1) {
start = 0; end = vals.length; inc = 1;
} else {
start = vals.length - 1; end = -1; inc = -1;
}
Stack < Integer> bigger = new Stack<>();
for (int i = start; i != end; i += inc) {
while (!bigger.empty() && vals[bigger.peek()]  <  vals[i]) {
bounds[bigger.pop()] = i + 1;
}
bigger.push(i);
}
return bounds;
}
}
``````
Copy The Code &

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});

process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());

main();
});

return inputString[currentLine++];
}

// Complete the solve function below.
function solve(arr) {
const left = new Array(arr.length).fill(0);
const right = new Array(arr.length).fill(0);

let stack = [];
for (let i = 0; i  <  arr.length; i += 1) {
while (stack.length) {
const index = stack.pop();
if (arr[i]  <  arr[index]) {
left[i] = index + 1;
stack.push(index);
break;
}
}
stack.push(i);
}

stack = [];
for (let i = arr.length - 1; i >= 0; i -= 1) {
while (stack.length) {
const index = stack.pop();
if (arr[i]  <  arr[index]) {
right[i] = index + 1;
stack.push(index);
break;
}
}
stack.push(i);
}

let max = 0;
for (let i = 0; i  <  arr.length; i += 1) {
max = Math.max(max, left[i] * right[i]);
}

return max;
}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

let result = solve(arr);

ws.write(result + "\n");

ws.end();
}
``````
Copy The Code &

#5 Code Example with Python Programming

```Code - Python Programming```

``````
n=int(input())
a=list(map(int,input().split()))
a.insert(0,None)
left={}
right={}
left[1]=0
right[n]=0
for i in range(2,n+1):
if a[i]==a[i-1]:
left[i]=left[i-1]

elif a[i] < a[i-1]:
left[i]=i-1

else:
if left[i-1]==0:
left[i]=0
else:
counter=i-1

while True:
leftNumber=a[left[counter]]

if left[counter]==1:
if a[1]>a[i]:
left[i]=1
else:
left[i]=0
break

if leftNumber==a[i]:
left[i]=left[left[counter]]
break

elif leftNumber>a[i]:
left[i]=left[counter]
break

else:
if left[left[counter]]==0:
left[i]=0
break
else:
counter=left[counter]

for i in range(n-1,0,-1):
if a[i]==a[i+1]:
right[i]=right[i+1]

elif a[i] < a[i+1]:
right[i]=i+1

else:
if right[i+1]==0:
right[i]=0
else:
counter=i+1

while True:
rightNumber=a[right[counter]]

if right[counter]==n:
if a[n]>a[i]:
right[i]=n
else:
right[i]=0
break

if rightNumber==a[i]:
right[i]=right[right[counter]]
break

elif rightNumber>a[i]:
right[i]=right[counter]
break

else:
if right[right[counter]]==0:
right[i]=0
break
else:
counter=right[counter]

maxProduct=0

for i in range(1,n):
product=left[i]*right[i]

if maxProduct < product:
maxProduct=product

print(maxProduct)
``````
Copy The Code &