WAP to Find Maximum Difference between two Index of array such that value at 1st index is less then value at 2nd Index, Efficiently

WAP to find out maximum j-i such that a[i]
Method 1

Algorithm
Use two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.


#include
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
struct maxdif
{
int i;
int j;
int maxDiff;

};
struct maxdif maxIndexDiff(int a[],int n)
{
struct maxdif maxdif;
maxdif.maxDiff=-1;
int i=0,j=0;
for(i=0;i {
for(j=n-1;j>0;j--)
{
if(a[i] {
maxdif.i=i;
maxdif.j=j;
maxdif.maxDiff=j-i;
}
}
}
return maxdif;
}

int main()
{ int ar[]={9,2,3,4,5,6,7,8,20,1};
int n=sizeof(ar)/sizeof(int);
struct maxdif max_diff=maxIndexDiff(ar,n);
printf(" j=%d i=%d maximum difference=%d", max_diff.j,max_diff.i,max_diff.maxDiff);
return 0;
}

Worst Case O(n^2)
Input: {1, 2, 3, 4, 5, 6}
Output: 5 (j = 5, i = 0)

Best Case O(n)
Input: {6, 5, 4, 3, 2, 1}
Output: -1

Time Complexity: O(n^2)
Space Complexity O(1)
Run Here https://ideone.com/lzIEd

Method 2 (Algorithm Given By Celicom


Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i2) Create array C[N]. Init it this way:
C[N-1] = A[N-1];
for(i=N-2;i>=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(jwhile(B[i] < C[j] && jmax_i_j = max(max_i_j,j-i);
i=i+1;j=j+1;
}

so To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.


#include
 
/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}
 
int min(int x, int y)
{
    return x < y? x : y;
}
 
/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;
 
    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);
 
   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);
 
    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);
 
    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }
 
    return maxDiff;
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = {9,2,3,4,5,6,7,8,20,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}


Time Complexity O(n)
Space Complexity O(n)
Ryun Here https://ideone.com/vQOMi