题目描述

给定正整数数组A，A[i]表示第i个观光景点的评分，并且两个景点i和j之间的距离为j-i。

一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。

返回一对观光景点能取得的最高分。

思路与算法

方法一：暴力枚举

我们可以通过枚举任意两点之间的评分之和，然后取其中最高分，但是当数组元素较多时，会超时。

方法二：动态规划

首先考虑如何优化上述遍历的双重循环问题，可以采用空间换时间的方法，通过一次遍历计算当前位置的最高分。

我们观察得分公式为A[i] + A[j] + i - j，可以将其拆分成两部分(A[i] + i) + (A[j] - j)，先用两个数组预先保存对应下标i的A[i] + i和A[i] - i。接着进行一遍遍历，记录当前位置j之前的A[i] + i能得到的最大值，并与当前位置的A[j] - j相加，得到当前位置能取得的最大值，直到一遍遍历结束后，即可得到整体的最高分。下面展示状态转移方程：

dp[j] = max(A[i] + i) + (A[j] - j) (i < j)

dp[j]指在下标为j的位置可以得到的最高评分。

代码

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int n = A.size();
        vector<int> V1(n);
        vector<int> V2(n);
        for(int i = 0; i < n; i++){
            V1[i] = A[i] + i;
            V2[i] = A[i] - i; 
        }
        int x = V1[0], ans = 0;
        for(int i = 1; i < n; i++){
            ans = max(x + V2[i], ans);
            x = max(x, V1[i]);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：一遍元素的遍历，故时间复杂度为O(n)。
• 空间复杂度：两个辅助空间V1和V2，故空间复杂度为O(n)。

改进与优化

上述计算每个位置的最高得分，只与此前的最大A[i] + i以及当前位置的A[j] - j有关，因此，我们可以用两个变量来记录这两个值，从而减少了上述方法中辅助空间的使用。

代码

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int n = A.size();
        int x = A[0] + 0, ans = 0;
        for(int i = 1; i < n; i++){
            ans = max(x + A[i] - i, ans);
            x = max(x, A[i] + i);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：一遍元素的遍历，故时间复杂度为O(n)。
• 空间复杂度：常数个变量，故空间复杂度为O(1)。