How can I efficiently find the largest positive interval in an unsorted array? [duplicate]

Question

This question already has an answer here:

• Finding a O(n) solution to: max difference of pairs array question [closed] 2 answers

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.