如何返回导致列表中两个元素之间的最大差值的指标？

Question

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)

如果给定列表[12, 9, 18, 3]，则我将计算任意两个元素i，j之间的最大差，以使j> i和j处的元素减去i处的元素具有最大差。

在这种情况下，我们有j = 2, i = 1，代表18 - 9是9的最大差异。

我当前的算法返回9，但我希望它返回指标(1,2)。如何修改这种分而治之的方法来做到这一点？

Answer 1

尝试一下：

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)