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).