Python: Maximum difference between elements in a list

user_7773783 0
Viewed 20176

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?

python-3.x algorithm
4 Answers

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.

user_105591420

using the new walrus operator (Python >3.8 req)

    import sys
    lst = [7,1,5,4]
    
    minscan = sys.maxsize
    solution = max([x - (minscan := min(minscan,x)) for x in lst])
    print(solution if solution !=0 else -1)
user_85447780 
def maxPairDiff(arr):
    listDiff=[]
    for p,i in enumerate(arr):
        evalList=[e for e in arr[p+1:] if e>i]
        if len(evalList)>0:
            listDiff.append(max(evalList)-i)
    return (max(listDiff))


givenList = [7, 9, 5, 6, 3, 2]
print ("Required result is {}".format(maxPairDiff(givenList)))
user_125236440

There are though many ways to solve a single problem. i would suggest this way as will be a bit faster and is more pythonic.

mylist = [2, 3, 8, 0, 7]
max_diff = max( [mylist[i+1]-mylist[i] for i in range(len(mylist)-1) if mylist[i]<mylist[i+1]] )

print(max_diff)
user_73589090
Related