Given an array A[], find (i, j) such that A[i] < A[j] and distance (j - i) is maximum.

Approach:
Example array:
int [] A = {6,5,9,15,29,7,4};


Create another array which has all the min elements to the left of  any i (0<=i<len(A)-1)
Lets call that array as B.
for (int i=1,k=0; i<len(A); i++,k++) {
     B[k] = Math.min(A[i],A[i-1]);
}
So now B would look like:
B = {5,5,9,15,7,4}


Similarly create another array say C which has all the max elements to the right of j
for (int i=len(A)-2, k=len(A)-2; i>=0; i--,k--) {
     C[k] = Math.max(A[i], A[i+1]);
}
Now array C would look like:
C = {6,9,15,29,29,7}


Now, compare each of B with C, by keeping track of max distance of i and j seen so far.
This would be like:


maxDistance = 0;
while (i<len(B) && j<len(C)) {
      if (B[i] < C[j]) {
              maxDistance = Math.max(maxDistance, j-i);
       }
}


Output:

Max Distance: 5
i:1   j:5