Finding largest farthest increasing pairs in array?
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.