How can I efficiently find the largest positive interval in an unsorted array? Given a set of values like [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an interval of 4 because 8 - 4 = 4. But the largest positive interval is between index 2 and index 10, because 11 - 1 = 10.

I can see that there's a way to do this in linear time, but I can't figure out what it is. The n^2 brute force solution is straightforward, but I want to understand the better way.



To be clear, the largest positive interval in [20, 1, 4] would be 3, not 19, because 20 -> 1 is an interval of -19.



The solution I would put forward is to translate the array in linear time to an array of differences, e.g. [20, 1, 7, 4, 2] becomes [0, -19, 6, -3, -2], and then use Kadane's algorithm for finding the maximum contiguous subsequence. The largest subsequence would be 6 on its own, implying indices 1 and 2 provided the answer.
Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned.

Here is the Python code for the simple linear algorithm hinted. Hit the "run" button to see a couple of test result.