Maximum Index-Asked In Google

Problem Statement :

Given an array A[] of N positive integers.

The task is to find the maximum of j — i subjected to the constraint of

A[i] < A[j] and i < j.

Input Format

The first line of the input contains an integer ’N’, denoting the total number of elements of the array.

The second line of the input contains the integer array.

Output Format:

The output consist of one line containing the maximum value of j-i, such that

A[i] < A[j] and i < j.

Given:

9
34 8 10 3 2 80 30 33 1

Output:

6

Explanation of given Test Cases :

In the given array A[1] < A[7]
satisfying the required 
condition(A[i] < A[j]) thus giving 
the maximum difference of j - i 
which is 6(7-1).

Approach:

As we need the max difference j -i such that A[i]<= A[j], hence we do not need to consider element after the index j and element before index i.

Let's say, we get max difference for particular i and j. Then these conditions hold true.

• A[i] <= A[j]
• Any element before A[i] is larger than A[j], it would not make the max difference. Hence we do not consider any element before A[i].
• Any element after A[j] is smaller than A[i], it would not make the max difference. Hence we do not consider any element after A[j].

Now make two arrays named First and Second

First, will store smallest occurring element before the element
Second, will store largest occurring element after the element

Traverse the Second array, till the element in the second array is larger than or equal to the First array, and store the index difference. And if it becomes smaller, traverse the first array till it again becomes larger.

And store the max difference of this index difference.

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.