传送门

题目要求要从一组数据中找出两个值之和减去下标差最大的数。

看到这个题目，瞟一下范围，50000的范围可以尝试一下暴力：

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int n = A.size();
        int ans = -1;

        for(int i = 0; i < n-1; i++)
            for(int j = i+1; j < n; j++)
            {
                int tmp = A[i] + A[j] + i - j;
                ans = max(ans, tmp);
            }

        return ans;
    }
};

然后会悲哀的发现过不了，开始思考优化方法。

题目中的得分公式是：A[i]+A[j]+i-j，将其整理为A[i]+i+A[j]-j，不难发现它由两部分组成。前一部分仅与i有关，后一部分仅与j有关，并且其和的最大值显然等于两个部分的最大值之和。

之前暴力做法超时的原因是两次循环分别枚举i、j，使时间复杂度达到了O(n2)，其实这样的思路是没有问题的。

对于景点j，它的最大得分为i∈(0,j)中最大的A[i]+i加上自己的A[j]-j。也就是说，对于单个的j，在计算它的最终得分时变量仅是A[i]+i，那么就可以动态保存当前进度下最大的A[i]+i然后加上A[j]-j，最终就是最大值了。

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int ans = -1;
        int maxn = A[0];//初始化
        int n = A.size();

        for(int i = 1; i < n; i++)
        {
            //A[i]+i的范围是(0,j),所以这里先更新ans再更新maxn
            ans = max(ans, maxn + A[i] - i);
            maxn = max(maxn, A[i] + i);
        }

        return ans;
    }
};