# Find Maximum

Arrays

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array `A` of `N` positive integers. The task is to find the `maximum` of
`j - i` such that `A[j] > A[i]`, where `j > i`.

See original problem statement here

#### For Example :

``````Input : N = 10, A[] = [5 16 7 3 2 9 10 4 3 4]

Output : 6

Explanation :

16 > 5, diff = 1 - 0 = 1
7 > 5,  diff = 2 - 0 = 2
9 > 5,  diff = 5 - 0 = 5
9 > 7,  diff = 5 - 2 = 3
10 > 5, diff = 6 - 0 = 6
4 > 2,  diff = 7 - 4 = 1
3 > 2,  diff = 8 - 4 = 4
4 > 2,  diff = 9 - 4 = 5

Out of all these differences, 6 was the maximum difference between indexes of 5 and 10 i.e. 6 - 0 = 6``````

#### BRUTE FORCE METHOD:

1. This method is `Simple` but `Inefficient`.

2. Run two nested loops.

3. In the outer loop, pick elements one by one from left to right.

4. In the inner loop, pick the rest of the elements and keep comparing the `maximum` value of `(j-i)`.

5. `Time complexity` of this approach is `O(N^2)`.

#### EFFICIENT METHOD:

1. The problem can be solved by simply finding out two `Optimum Indexes of the array`, `left index` `i` and `right index` `j` by referring the best online classes for coding.

2. For an element `A[i]`, we need not consider it for the left index if there exists a smaller element than `A[i]` on its left side.

3. Similarly for an element `A[i]`, we need not consider it for the right index if there exits a greater element on its right side.

4. Now construct two arrays : `leftMin[]` and `rightMax[]`,
such that `leftMin[i]` contains the smallest element on its left side including itself and `rightMax[i]` contains the largest element on its right side including itself.

5. Start traversing both the arrays from left to right.

6. While traversing :-

if `leftMin[i]` `>` `rightMax[i]`, then we simply move ahead in `leftMin[]` by `1`, as all elements to the left of `leftMin[i]` are either greater than or equal to `leftMin[i]`

if `leftMin[i]` `<` `rightMax[i]`, then we move ahead in `rightMax[i]` to look for a better value of `j-i`.

### MAXIMUM

```#include<stdio.h>

int maximumGap(int arr[],int n) {
int l[n],r[n];
l=arr;
for(int i=1;i<n;i++)
{
if(arr[i]<l[i-1])
l[i] = arr[i];
else
l[i] = l[i-1];
}
r[n-1]=arr[n-1];
for(int i=n-2;i>=0;i--)
{
if(arr[i] > r[i+1])
r[i] = arr[i];
else
r[i] = r[i+1];
}
int i=0,j=0;
int max_dist = -1;
while(i<n && j<n)
{
if(l[i]<r[j])
{
if(j-i > max_dist)
max_dist = j-i;
j++;
}
else
{
i++;
}
}
if(max_dist==-1)
return -1;
return max_dist;
}

int main()
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("%d\n",maximumGap(arr,n));

return 0;
}

```
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int maximumGap(int arr[],int n) {
int l[n],r[n];
l=arr;
for(int i=1;i<n;i++)
{
l[i]=min(arr[i],l[i-1]);
}
r[n-1]=arr[n-1];
for(int i=n-2;i>=0;i--)
{
r[i]=max(arr[i],r[i+1]);
}
int i=0,j=0;
int max_dist = -1;
while(i<n && j<n)
{
if(l[i]<r[j])
{
max_dist = max(max_dist,j-i);
j++;
}
else
{
i++;
}
}
if(max_dist==-1)
return -1;
return max_dist;
}

int main()
{
int n;cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<maximumGap(arr,n)<<"\n";

return 0;
}

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

public class Main {

static int maximumGap(int arr[],int n) {
int l[] = new int[n];
int r[] = new int[n];
l=arr;
for(int i=1;i<n;i++)
{
l[i]=Math.min(arr[i],l[i-1]);
}
r[n-1]=arr[n-1];
for(int i=n-2;i>=0;i--)
{
r[i]=Math.max(arr[i],r[i+1]);
}
int i=0,j=0;
int max_dist = -1;
while(i<n && j<n)
{
if(l[i]<r[j])
{
max_dist = Math.max(max_dist,j-i);
j++;
}
else
{
i++;
}
}
if(max_dist==-1)
return -1;
return max_dist;
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
arr[i] = sc.nextInt();
System.out.println(maximumGap(arr,n));
}
}

```