biggest decrease list from O(n^2) to O(n)

Question

My program has complexity O(n^2). I want to have this pogram in complexity O(n). How can I achieve that?

The idea behind my program is that I want to have the biggest decrease in a list from an element, compared with the ones that are after that element.

So for example the list [4,7,5,8,4,3] compares element 4 with 7,5,8,4,3 and compares element 8 with 4,3. The solution would be; 8-3 = 5 (the biggest decrease).

def grootste_daling(temperaturen):
    afname = []
    for i in range(len(temperaturen)):
        for j in range(i + 1, len(temperaturen),1):
                if temperaturen[i] - temperaturen[j] > 0:
                    afname.append(temperaturen[i] - temperaturen[j])
    return max(afname) if afname else 0

Answer 1

Yes, this is solvable in linear time. You only need to keep track of the biggest element seen so far:

    maximum = 0
    max_decrease = 0
    for current in temperatures:
        if current > maximum:
            maximum = current
        if maximum - current > max_decrease:
            max_decrease = maximum - current

(The initial values of 0 assume that the values of the list will be positive and that there will be an actual decrease. Otherwise the variables may need to be initialized differently.)