CODEWITHSUNDEEP
pythonalgorithmlistdivide-and-conquer
K Split X
K Split X

Reputation: 4727

Returning indicies for the values producing the max difference

I have a recursive function, that finds the maximum difference between any two integers, provided that the value at the second index is higher than the value at the first index:

def func(arr):
    if len(arr) <= 1:
        return 0;

    left  = arr[ : (len(arr) // 2)]
    right = arr[(len(arr) // 2) : ]

    leftBest  = func(left)
    rightBest = func(right)

    crossBest = max(right) - min(left)

    return max(leftBest, rightBest, crossBest)

If I am given the list [12, 9, 18, 3], then I would compute the maximum difference between any two elements i, j such that j > i and the element at j minus the element at i is of max difference.

In this case we have j = 2, i = 1, representing 18 - 9 for the biggest difference of 9.

My current algorithm returns 9, but I would like it to return the indicies (1, 2). How can I modify this divide and conquer approach to do this?

Upvotes: 1

Views: 220

Answers (3)

Martijn Pieters
Martijn Pieters

Reputation: 1121744

Instead of returning the maximum difference, return both the indices and the maximum difference. Because you pass in sliced lists to the recursive calls, you'll have to adjust the indices returned from recursive rightBest calls (the leftBest calls always start with a list running from 'current' 0 to the midpoint).

Use min() and max() with a key that alters how the maximum is picked. For picking the index of the maximum value in a a list, generate the indices with range(), then map those indices back to the list with arr.__getitem__:

def func(arr):    
    if len(arr) <= 1:
        return 0, 0, 0

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    leftBest  = func(left)
    ri, rj, rm = func(right)
    rightBest = (ri + mid, rj + mid, rm)

    key = arr.__getitem__
    ci = min(range(0, mid), key=key)
    cj = max(range(mid, len(arr)), key=key)
    crossBest = (ci, cj, arr[cj] - arr[ci])

    return max(leftBest, rightBest, crossBest, key=lambda ijm: ijm[2])

This returns the 2 indices as well as the difference:

>>> func([12, 9, 18, 3])
(1, 2, 9)

You'd have to slice the result to get just the i, and j values:

>>> func([12, 9, 18, 3])[:2]
(1, 2)

I'd not even slice the arr list, because there is really no need to create copies here. Just pass along start and stop indices to the recursive functions to replace 0 and len(arr). I'd also use a nested function to do the recursive work; the outer function can be used to extract just the (i, j) pair:

def best_difference_indices(arr):
    arr_get = arr.__getitem__
    max_get = lambda ijm: ijm[2]

    def _func(start, stop):
        if stop - start <= 1:
            return start, start, 0

        mid = (stop - start) // 2 + start
        left_best = _func(start, mid)
        right_best = _func(mid, stop)

        ci = min(range(start, mid), key=arr_get)
        cj = max(range(mid, stop), key=arr_get)
        cross_best = (ci, cj, arr[cj] - arr[ci])

        return max(left_best, right_best, cross_best, key=max_get)

    i, j, _ = _func(0, len(arr))
    return i, j

Not having to slice makes this faster; with an input of 1000 elements, the second version takes < 3ms to find the 2 indices, while the version with slicing takes ~3.6 ms; a 20% increase.

For 1 million elements, that becomes 3.7 seconds and 4.22 seconds, respectively.

Upvotes: 1

user2390182
user2390182

Reputation: 73460

I don't know if you are nailed to a recursive divide'n'conquer implementation. If you are not, here is an iterative, linear solution:

def func(arr):
    min_i = lower_i = 0
    max_dif = upper_i = None
    for i in range(1, len(arr)):
        if max_dif is None or max_dif < arr[i] - arr[min_i]:
            max_dif = arr[i] - arr[min_i]
            lower_i = min_i
            upper_i = i
        if arr[i] < arr[min_i]:
            min_i = i
    return lower_i, upper_i

Upvotes: 2

tjholub
tjholub

Reputation: 714

Try this:

In [1] arr = [12, 9, 18, 3]

In [2]: diff = 0                                                                                                                                    

In [3]: for i in range(len(arr)): 
    ...:     for j in range(i): 
    ...:         tmp = arr[i] - arr[j] 
    ...:         if tmp > diff: 
    ...:             diff = tmp 
    ...:             result = j, i 
    ...:              
    ...:          
    ...:                                                                                                                                             

In [4]: result                                                                                                                                      
Out[4]: (1, 2)

Upvotes: -1

Related Questions