1014.最佳观光组合

1014. 最佳观光组合

难度中等84

给定正整数数组 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

提示：

1. 2 <= A.length <= 50000

2. 1 <= A[i] <= 1000

   解题思路
   我们考虑从前往后枚举j来统计答案，对于每个观光景点j唁,我们需要遍历[0,j一1]的观光景点i来计算组成观光组
   合(i,i)得分的最大值cntj来作为第j个观光景点的值,那么后的答案无疑就是所有观光景点值的最大值,即
   maxj-=0.n- 1{cntj}。但是枚举j要O(n)的时间复杂度,遍历[0,j一1]的观光景点i也需要O(n)的时间复杂度,
   因此该方法总复杂度为O(n2 ),不能通过所有测试用例，我们需要进一步优化时间复杂度。
   我们回过头来看得分公式，我们可以将其拆分成A[i]+ i和A[j]- j两部分,这样对于统计景点j答案的时候,纡
   A[j]- j固定不变的，因此最大化A[i+i+ A[j]- j的值其实就等价于求[0,j- 1]中A[i]+i的最大值mx,景
   点j的答案即为mx+ A[j]- j。而mx的值我们只要从前往后枚举j的时候同时维护即可,这样每次枚举景点j的时
   候，寻找使得得分最大的i就能从O(n)降至0(1)的时间复杂度，总时间复杂度就能从O(n2)降至O(n)。
   

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int ans = 0, mx = A[0] + 0;
        for (int j = 1; j < A.size(); ++j) {
            ans = max(ans, mx + A[j] - j);
            // 边遍历边维护
            mx = max(mx, A[j] + j);
        }
        return ans;
    }
};