algorithm - 找到向量中的最大距离

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)。第一项仅是 p 的函数，第二项仅是 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