Returning indicies for the values producing the max difference

Question

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?

If you search in your browser for "Optimum stock buy sell", you'll find references that can explain this much better than we can manage here. Make sure you check for unlimited purchase and single sale. This is a common homework problem. — Prune, Oct 15 '19 at 16:27
Returning the indices is exactly that: return each index, rather than the values. If you don't keep the index when you locate the value, then use `index` to retrieve it. — Prune, Oct 15 '19 at 16:31

score 2 · Answer 1 · answered Oct 15 '19 at 17:26

2

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

answered Oct 15 '19 at 17:26

user2390182

72,016
6
67
89

Nice. Doesn’t answer the direct question but a linear time solution is nonetheless great :-) I wish I had had the time this afternoon to have worked out a linear approach, but alas. – Martijn Pieters Oct 15 '19 at 23:56

Martijn Pieters · Answer 2 · 2019-10-15T17:26:14.160

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.

score -1 · Answer 3 · answered Oct 15 '19 at 16:16

-1

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)

answered Oct 15 '19 at 16:16

tjholub

678
4
7

This is a less efficient solution, the OP has a O(N log N) approach, yours is O(N^2). So for an input of 1000 elements, theirs takes ~7000 steps, yours approaches *1 million* steps (and yes, the real number is a [triangle number](https://stackoverflow.com/questions/3179338/big-o-notation-for-triangular-numbers) but we are talking about asymptotic behaviour). – Martijn Pieters Oct 15 '19 at 16:51
The corrected version of the OP algorithm takes 3.6 ms for 1000 items, my no-slicing version takes just under 3 ms. Your version takes 47 ms. For 1 million items, the times are 4.2 seconds, 3.7 seconds, and I am still waiting for a time from your version. It'll be a while, as it'll take more than 25000 times longer, I'm not sure if I want to wait more than a day! – Martijn Pieters Oct 15 '19 at 17:03

Returning indicies for the values producing the max difference

3 Answers3