[Math] Largest Difference of Two Numbers in an Array

Question

Given an integer sequence $s_1,s_2,…,s_n$, I want to find $\max(s_j-s_i)$, where $j>i$.

I wrote the following algorithm (s is a $1$-based array with n elements):

max = 0
for i from 1 to n - 1
    for j from i + 1 to n
        if s[j] - s[i] > max
            max = s[j] - s[i]

It works, but it runs in $O(n^2)$ time. Is there an $O(n)$ algorithm? Is this a disguised instance of the maximum subarray problem?

Answer 1

EDIT: Realized my prior algorithm was flawed. This new one should be right.

EDIT 2: And a second flaw was pointed out years later (despite its simplicity). Thanks @gfppoy

There is an $O(n)$ algorithm broken down into two cases. (Note that figuring out which of the two cases we're in boils down to figuring out whether an array is strictly decreasing, which is itself $O(n)$)

Case 1: The array is strictly decreasing. In this scenario, we simply compare pairs of adjacent numbers and return the value corresponding to the "closest" two.

Case 2: Everything else

Loop through the array, keeping track of the maximum element. The catch is, now we "reset" the maximum every time we find a new minimum element. Something like this in pseudocode:

max_difference = 0
min = s[0]
max = s[0]

for i = 1 to s.length - 1
    if s[i] < min
        min = s[i]
        max = s[i]
    else
        max = max(s[i], max)
        max_difference = max(max - min, max_difference)

That way, for each new "maximum" we find, we associate it with the smallest element to its left, and for that minimum element, we are only considering maxima to its right (and if we don't compare it with a maximum to its right, it will be because we found a smaller element that is still to the left of that maximum).

---

NB: It's possible to modify the pseudocode to make it cover both cases and still be $O(n)$. I've not done so since reasoning out the correctness of that code becomes unnecessarily complicated; the algorithm presented here is just easier to read and reason about.