博客

题意：

给定正整数数组

A

，

A[i]

表示第

i

个观光景点的评分，并且两个景点

i

和

j

之间的距离为

j - i

。

一对景点（

i < j

）组成的观光组合的得分为（

A[i] + A[j] + i - j

）：景点的评分之和

减去

它们两者之间的距离。

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

解法：

因为要求A[I]+A[J]+i-j的最大值，就是求A[J]-J+A[I]+I的最大值，那么从后往前扫描一遍，在扫描的过程中记录之前扫描的所有值中最大的A[J] – J就可以了，假设记录在变量maj中。然后对于每个i位置，因为maj就是i位置之后的最大的A[J]-J，所以就只需要用maj+a[i]+i算一下值就可以得到当i取i时候，A[J]-J+A[I]+I得到的最大值。然后在遍历的时候同时维护一下这个得到的最大值就ok了。

代码：

class Solution {
public:
int maxScoreSightseeingPair(vector<int>& A) {
    int maj=0,mai=0,ma=0;
    int sz = A.size();
    maj = A[sz-1]-sz+1;
    for(int i=sz-2;i>=0;i--){
        ma = max(ma,maj+A[i]+i);
        maj = max(maj,A[i]-i);
    }
    return ma;
}
};