Учитывая несортированный массив, найдите максимальное вычитание между двумя элементами в массиве

Question

Я получил этот вопрос из интервью в Microsoft: учитывая несортированный массив, найти максимальное вычитание между двумя элементами в массиве можно следующим образом:

(Index1, Index2) = arr[Index2] - arr[Index1].    Index1<Index2.

Пример:

given the array: [1, 5, 3, 2, 7, 9, 4, 3] -> Output: (1,9)=8.
given the array: [4, 9, 2, 3, 6, 3, 8, 1] -> Output: (2,8)=6.

Наивное решение работает за O(n^2) раз: отсканируйте первый индекс для вычитания со всеми другими индексами и сохраните максимальное значение, перейдите к следующему индексу и так далее.

Есть ли способ оптимизировать это?

Answer 1

Довольно просто, когда вы записываете это. Перефразируя проблему, вы хотите найти самый большой элемент справа от каждого элемента. Теперь, учитывая первый пример, это:

[1, 5, 3, 2, 7, 9, 4, 3]
=>
[9, 9, 9, 9, 9, 4, 3]

Теперь обратите внимание, что массив максимумов - это всего лишь кумулятивные максимумы справа. Учитывая это свойство, легко построить O(n) алгоритм времени.

Реализация на питоне:

def find_max(xs):
    ys = []
    cur_max = float('-inf')
    for x in reversed(xs):
        cur_max = max(x, cur_max)
        ys.append(cur_max)
    ys = ys[::-1][1:]
    return max(y - x for x, y in zip(xs, ys))

Мы также можем лениво построить массив максимумов, что дает нам O(1) память, которая является лучшей из возможных:

def find_max(xs):
    cur_max = float('-inf')
    cum_max = xs[-1]
    for i in range(len(xs) - 2, -1, -1):
        cur_max = max(cur_max, cum_max - xs[i])
        cum_max = max(cum_max, xs[i])
    return cur_max

Answer 2

Я думаю, что это правильно, и O(nlogn): разделить в середине и выбрать справа максимум, слева значение min. Также разделите остальные 2 квартала, если один из них даст больший результат, продолжайте рекурсивно.

Второй пример:

4, 9, 2, 3| 6, 3, 8, 1 -> 2 and 8
4, 9| 2, 3, 6, 3, 8, 1 -> 4 and 8
4, 9, 2, 3, 6, 3| 8, 1 -> 2 and 8

Итак, работа над правильным разделением:

4, 9, 2, 3, 6, 3, 8| 1 -> 2 and 1

Выбор 2 а также 8 вариант. Это также работает для первого примера.