2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Find the difference between the maximum and the minimum $\endgroup$ – LeeNeverGup Nov 4 '13 at 16:33
  • 2
    $\begingroup$ @LeeNeverGup No, because the maximum element might be to the left of the minimum element. $\endgroup$ – MJD Nov 4 '13 at 16:33
  • 1
    $\begingroup$ @JosueMolina Thanks for the catch, you're right; that last line was wrong. Sorry I wasn't around when you made it; I would've approved it. $\endgroup$ – Dennis Meng Nov 4 '13 at 20:18
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This fails for a strictly decreasing array (ex. {5, 4, 1}) $\endgroup$ – gfppoy Sep 15 '17 at 18:15
  • $\begingroup$ @gfppoy Hmm, yes, you're right. It's bedtime here, so I'll fix it up in the morning. $\endgroup$ – Dennis Meng Sep 16 '17 at 8:22
  • $\begingroup$ Why not just keep track of "minimum number seen so far" and subtract that from the current element at each iteration to see if we find a better difference? $\endgroup$ – Henning Makholm Sep 16 '17 at 23:42
1
$\begingroup$

While the accepted O(n) perfectly answers the question, it might be of interest that there also exists an O(logn) algorithm after O(n) precomputation that can also handle subarrays and updates.

The implementation can be done with segment trees by keeping the minimum, maximum and max(sj−si) of the subarray stored at every node. This allows for a query that checks every relevant subtree and finds all deltas inside and between the subtrees.

My C++ implementation

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.