Find the largest decrease in a sequence of numbers

Question

I have written a function that takes as input a list of 5 numbers, then the program's goal is to return the largest drop in the list. It is important to understand that [5, 3, ...] is a decrease of 2 and that [5, 20, .....] is a decrease of 0. In short, a decrease can only be from left to right and the largest decrease can for example also be the decrease from the 1st number to the 4th number, they do not necessarily have to be next to each other.

def biggest_drop(temperature):
 difference = 0
 new_temperature = temperature.copy()
 a = 0
 for i in temperature: 
 del new_temperature[0]
 for j in new_temperature:
 if i <= j:
 False
 else:
 a = i - j
 if a > difference:
 difference = a
 return difference

The good news is the code works, the bad news is that because of the double for loop there is already a Big-O notation of O(n²). However, the program must have a Big-O notation of O(n¹) and I don't know how to fix this and where the speed of the code is also high enough. For example, here I have made a fairly sloppy alternative, but it is too slow:

def biggest_drop(temperature):
 difference = 0
 a = 0
 b = temperature[1]
 c = temperature[2]
 d = temperature[3]
 e = temperature[4]
 for i in temperature:
 if temperature[0] <= temperature[1] <= temperature[2] <= temperature[3] <= temperature[4]:
 return 0
 elif i > b:
 a = i - b
 if a > difference:
 difference = a
 elif i > c:
 a = i - c
 if a > difference:
 difference = a
 elif i > d:
 a = i - d
 if a > difference:
 difference = a
 elif i > e:
 a = i - e
 if a > difference:
 difference = a
 return difference

Do you have a better idea how my code complies with the big-O notation of O(n¹) and is also fast enough for larger n, in other words lists with more than 5 integers?

• Martin R: Welcome to Code Review! – The site standard is for the title to simply state the task accomplished by the code, not your concerns about it. Please see How do I ask a good question? for examples, and revise the title accordingly.
• Martin R: Btw, what is n if the input is always a list of 5 numbers?
• yungCalculator: apologies, I only now understand from the command that the one larger n creates a larger list of integers
• Martin R: Which a quick Google search I found this math.stackexchange.com/a/1172157/42969 and this stackoverflow.com/q/15019851/1187415, which might be what you are looking for.

Answer 1

This can be solved in a single pass, e.g., O(n).

For each temperature, subtract it from the highest temperature seen so far to get the drop. Keep track of the largest drop. Also update the highest temperature.

def biggest_drop(temperatures):
 highest = temperatures[0]
 largest_drop = 0
 for temperature in temperatures:
 drop = highest - temperature
 largest_drop = max(largest_drop, drop)
 highest = max(temperature, highest)
 return largest_drop