Algorithm to maximize $j-i$ subject to $A[j]>A[i]$

Question

We want an algorithm that, given an array $A$ of length $n$ of integers (indexed by $A[0],A[1],\ldots,A[n-1]$, determine values $i<j$ that maximizes $j-i $ subject to $A[j]>A[i]$ (if such values $i,j$ exist.)

One possibility is as follows: First check whether the array is non-increasing. If so, no such $i,j$ exist. Else, iterate through the elements from front to back, keeping a running array which we append the current element if it is the minimum so far. This running array is decreasing, and we can use binary search to find the greatest element that's less than the current element. We update $j-i$ if it beats the previous maximum. This takes time $O(n\log n)$ because of binary search.

Is there a faster way, e.g., an $O(n)$ algorithm?

Answer 1

As you mention, the candidate $i$s are those who are left-to-right minima, and they form a decreasing sequence. Similarly, the candidate $j$s are right-to-left maxima, and they form an increasing sequence going from right to left (so a decreasing sequence in the usual order). Now imagine keeping two points, one on the left-to-right minima, starting at the leftmost, and another on the right-to-left maxima, starting at the rightmost. Is there a way to traverse both lists in $O(n)$, answering your question on the way?