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] &gt; 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).
I'm going to assume that in your question, $i &gt; j$ holds as well (if there is no such pair of values, then you have a nonincreasing array and the problem is trivial). 

The two alternatives you've pointed out in your post are


$O(n)$ additional memory and $O(n)$ time
$O(1)$ additional memory and $O(n^2)$ time


An "intermediate" solution, for example, is to pick $O(\frac{n}{B} + B)$ additional memory and $O(n \cdot \left(\frac{n}{B} + B)\right)$ time. To do this, divide the array into continguous blocks of size $O(B)$, and so the number of blocks is $O(\frac{n}{B})$. For each block, store only the minimum value of the block in an array block_minimum.

Say you're at the $i$-th index. The goal is to find the first index in the array where the value of the corresponding element is greater than A[i]. 

First, for all preceding blocks, find the first block $j$ for which block_minimum[j] &lt; A[i]. If such a block exists, scan that block and find the first index $k$ belonging to the block for which A[k] &lt; A[i]. The index $k$ is the first index of the array for which A. There are $O(\frac{n}{B})$ preceding blocks.

However, if such a block doesn't exist, then second, iterate on preceding elements in the current block (there are $O(B)$ of them).

The combination of the two steps consumes $O(\frac{n}{B} + B)$ time for an index $i$. So the overall time usage is $O\left(n \cdot \left(\frac{n}{B} + B\right)\right)$ and the extra memory usage is $O\left(\frac{n}{B}\right)$ (the number of blocks).

If we choose $B = O(\sqrt n)$, we obtain a solution that uses $O(\sqrt n)$ memory and $O(n \sqrt n)$ time. This technique is commonly known as square-root decomposition.