Python: Maximum difference between elements in a list

Question

I need to find the maximum difference between elements in an unsorted list if the element to the right of the present element is greater. For eg:

myList = [2, 3, 8, 0, 7]. 

Function should calculate as follows:

present element = 2.
is 3 > 2? Yes. Then 3-2 = 1
is 8 > 2? Yes. Then 8-2 = 6
is 0 > 2? No. Go to the next element.
is 7 > 2? Yes. Then 7-2 = 5 and so on

Finally my output = 7

My first solution is as follows:

def maxDiff(a):
l = len(a)
arr = []
for i in range(l-1):
    for j in range(i+1, l):
        if a[j] > a[i]:
            diff = a[j] - a[i]
            arr.append(diff)
return (max(arr))

I was said that this is not an optimal solution. I came up with another solution which is as follows:

def maxDiff(a):
l = len(a)
diffList = []
for i in range(l-1):
    newList = a[i+1:]
    max1 = max(newList)
    difference = max1 - a[i]
    diffList.append(difference)
return (max(diffList))    

My question is is the second solution correct? If yes, then is it optimal? What is the time complexity of both these functions? Is there any other solution that is more optimal?

Answer 1

Your second solution still recalculates the max value of the prefix list on every iteration, which you don't need to do.

I think both of your solutions are correct, but the second one is still at least quadratic O(n^2) since you are performing linear-time operations (such as max()) in your for loop. So to answer your question: No, it's likely not an optimal solution.

If I understood the problem correctly, it can be solved using dynamic programming. Consider the following code:

def maxDiff(a):
    vmin = a[0]
    dmax = 0
    for i in range(len(a)):
        if (a[i] < vmin):
            vmin = a[i]
        elif (a[i] - vmin > dmax):
            dmax = a[i] - vmin
    return dmax

Here we are simply keeping track of the smallest value encountered so far, and the largest difference, thus allowing us to iterate only once through the list without the need for storing any additional lists or doing any nested looping. The runtime of this should therefore be linear, O(n), in terms of comparison operations.