题目描述

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例：

输入：[8,1,5,2,6]
输出：11
解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

解题思路

观光分组合A[i]+A[j]+i-j，也可以写成A[i]+i+A[j]-j。
在计算某一项j的最优组合时，从0到j-1看，需要找到前面最大的一项A[i]+i。这里可以取巧。避免每次计算新j的时候，从头开始遍历得到最大的i项。也就是，从j=1开始，使用mx记录前j-1项中最大的i项。这样就保证了O(n)的复杂度。

    int maxScoreSightseeingPair(vector<int>& A) {
        int mx = A[0];
        int ret = numeric_limits<int>::min();
        for(int j=1; j<A.size(); j++){
            ret = max(ret, mx + A[j]-j);
            mx = max(mx, A[j]+j);
        }
        return ret;
    }