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

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. Он также работает для первого примера.