# Finding largest farthest increasing pairs in array?

Is there a simple linear algorithm for finding in an array A two such elements that $$A[i] > A[j]$$ and $$i – j$$ is as large as possible? If one wants to actually return the indices, then linear memory usage seems impossible to avoid. If the only result needed is the value $$i – j$$, i.e. the distance, can we get away with less than linear memory?

Obviously, one can use constant memory if one is willing to loop over all pairs (i, j).