Найти наибольшее расстояние в векторе

Question

У меня есть массив положительных целых чисел. Проблема заключается в том, чтобы найти самое высокое расстояние в векторе. Расстояние вычисляется как A [p] + A [q] + (q - p), где A - вектор p, q - индексы и p < = q. Сложность решения должна быть O (n). Я могу решить эту проблему с помощью решения O (n^2), но я не могу найти алгоритм O (n) для этой проблемы.

Кто-то может мне помочь? Заранее спасибо. Какой язык используется для поиска решения, не имеет значения.

Answer 1

Переставить объект как (A [p] - p) + (A [q] + q). Первый член - это функция только от р, а второе слагаемое - функция только от q. Таким образом, они могут быть оптимизированы отдельно при условии p ≤ q. По мере увеличения q от 0 до n-1 наилучший выбор p можно вычислить из предыдущего наилучшего и A [q] - q.

def highest_distance(A): 
    highest = float('-inf') 
    max_Ap_minus_p = float('-inf') 
    for q in range(len(A)): 
     max_Ap_minus_p = max(max_Ap_minus_p, A[q] - q) 
     highest = max(highest, max_Ap_minus_p + (A[q] + q)) 
    return highest