Finding the biggest decrease in a list of integers (Python)

Question

Given an array of n integers, h0, . . . , hn−1, I want to find the largest decrease in values such that the largest decrease is max(hi − hj) such that i ≤ j.

For example, given as an input the array [20, 50, 100, 93, 80, 120, 110, 115, 100, 110, 90, 200, 175], the answer would be 120-90 = 30.

I know this is possible if we take the first value, scan the array, and find the greatest decrease from that value, then move to the second value and do the same, but would it be possible to do this in linear time?

EDIT:

Here's the algorithm I came up with, but it runs in O(n^2) time:

heights = [int(line) for line in sys.stdin]

hi = 0
for i in range(len(heights)):
    for j in range(i+1, len(heights)):
        if (heights[i]-heights[j]) > 0:
            hi = max(hi, heights[i]-heights[j])
print(hi)

Answer 1

Store the pair of values $(d, m)$, where $d$ is the largest decrease found so far, and $m$ is the largest value found in the array so far. Read through the array in linear time, updating the values by $(d', m') = (\max\{d, m - x\}, \max\{m, x\})$, where $x$ is the current value in the array.

Answer 2

Here's the best I could come up with on the spot:

Find the minimum. Say it's in position $j$. The find the max in the sub-array from $i=0$ to $j$. Store the result. Then find the minimum for elements whose index is $ \geq j$, say $k$, find the max in the sub-array from $j$ to $k$, and repeat the process until you hit the end of the array. At the end, compare the jump sizes among the different sub-arrays.

Edge case: this algorithm fails if the array is in ascending order.

Worst case runtime is still $O(n^2)$ though.