Cerinta completa

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.

Limbajul de programare folosit: cpp14

Cod:

#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;
}

Scor obtinut: 1.0

Submission ID: 464653876

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

Find Maximum Index Product