Возврат указателей для значений, создающих максимальную разницу

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

Я не знаю, прибегаете ли вы к рекурсивной реализации "разделяй и властвуй". Если нет, вот итеративное линейное решение:

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        

Answer 2

Вместо того, чтобы возвращать максимальную разницу, возвращайте как индексы, так и максимальную разницу. Поскольку вы передаете в рекурсивных вызовах нарезанные списки, вам придется корректировать индексы, возвращаемые рекурсивными вызовами rightBest (вызовы leftBest всегда начинаются со списка, начинающегося с 'current' 0 до средней точки).

Используйте min() и max() с ключом, который изменяет способ выбора максимума. Для выбора индекса максимального значения в списке, сгенерируйте индексы с range(), затем сопоставьте эти индексы обратно с списком с 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])

. Это возвращает 2 индекса, а такжеразница:

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

Вы должны нарезать результат, чтобы получить только значения i и j:

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

Я бы даже не нарезалarr список, потому что здесь нет необходимости создавать копии. Просто передайте индексы start и stop рекурсивным функциям, чтобы заменить 0 и len(arr). Я бы также использовал вложенную функцию для выполнения рекурсивной работы;внешняя функция может использоваться для извлечения только пары (i, j):

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

Отсутствие среза делает это быстрее;при вводе 1000 элементов вторая версия занимает <3 мс, чтобы найти 2 индекса, а версия с нарезкой занимает ~ 3,6 мс;увеличение на 20%. </p>

Для 1 миллиона элементов это составляет 3,7 секунды и 4,22 секунды соответственно.

Answer 3

Попробуйте это:

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)