算法

(线性扫描) $O(n)$

注意到$s=(A[i]+i)+(A[j]-j$)，前一部分只与$i$相关，后一部分只与$j$相关。于是我们就可以有$2$种做法，一种是固定$i$，去求右侧最大的$A[j]-j$的值，然后加上当前的$A[i]+i$，最后选出最大的那一个；第二种解法是固定$j$，去找左侧最大的$A[i]+i$，然后加上当前的$A[j]-j$，最后找出最大的那一个。这里只展示第二种解法。

Java 代码

class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        // s = A[i] + i + A[j] - j, i < j
        int maxLeft = A[0];
        int max = 0;
        for (int j = 1; j < A.length; ++j) {
            max = Math.max(max, maxLeft + A[j] - j);
            maxLeft = Math.max(maxLeft, A[j] + j);
        }
        return max;
    }
}