最大ij,所以A [i]> = A [j]

Question

让我们假设我们有一个正整数数组A. 我们的任务是找到具有以下属性的最大posible ij,i> j:A [i]> = A [j].

举个例子,如果

A[0]=78
A[1]=88
A[2]=64
A[3]=94
A[4]=17
A[5]=91
A[6]=57
A[7]=69
A[8]=38
A[9]=62
A[10]=13
A[11]=17
A[12]=35
A[13]=15
A[14]=20
A[15]=15

然后答案是10,因为对于i = 14和j = 4,A [i]> A [j].

哪个是最适合该任务的算法？

到目前为止,我已经考虑了以下算法:我应用mergesort.我使用变量max来存储最终答案.每当A [i]和A [j]未交换时,我检查ij> max.如果是这样,我会更新最大值.时间复杂度:O(nlogn).

有更好的算法吗？

Answer 1

我们可以在O(N)中为长度为N的数组执行此操作.

对于a i和j给予我们最大值i-j,我们必须具有A[i]比所有后续元素更多且A[j]少于所有先前元素的元素.否则,我们可以选择更晚A[i]或更早A[j],并获得更大i-j.

查找A大于所有后续元素的所有元素,以及A少于所有先前元素的所有元素:

j_candidates = [0]
for j in range(1, N):
    if A[j] < A[j_candidates[-1]]:
        j_candidates.append(j)

i_candidates = [N-1]
for i in reversed(range(N-1)):
    if A[i] > A[i_candidates[-1]]:
        i_candidates.append(i)
i_candidates.reverse()

然后,对于每个j候选人,找到最佳的相应i候选人,从前一个j候选人的最佳i候选人开始搜索.

best_distance = 0
i_candidate_index = 0
for j in j_candidates:
    while (i_candidate_index + 1 < len(i_candidates)
           and A[j] <= A[i_candidates[i_candidate_index+1]]):
        i_candidate_index += 1
    best_distance = max(best_distance, i_candidates[i_candidate_index] - j)