力扣1014.最佳观光组合题解

题解

• 题目
• • 思路
  • 代码
  • 三元素比较的算法代码（没有AC）

题目

思路

明显题目是想要考我们dp或者贪心算法。

我们可以从最基础的暴力算法来获得灵感。

暴力算法是通过固定每一个a[j]-j,来获得最大的a[i]+i。

那么我们可以通过贪心算法，设置一个int left，在迭代的每一步都实时更新最大的a[i]+i的值，这样就不用每一次j++都要遍历一次数组寻找left的最大值了。

当然，反过来，如果我们设置int right，然后迭代的每一步都实时更新最大的a[i]-i的值，也会在一次遍历的复杂度下取得结果。

我刚开始的做法是想通过设置left和right的值，在迭代的时候，同时比较三种情况：left与right，left与a[i]-i,left变成right后与a[i]-i.

比如7,8,8,10.

我期望在迭代到第二个8的时候，通过比较7+0,8-1；7+0,8-2；8+1,8-2；来找到最大的值，然后更新结果ans.但是在遇到比较复杂的样例：6,3,7,6,6,4,9.时，我的算法会在迭代到9的时候，left是前面的7+2，right是后面的6-3.最后结果明显没办法是（6+4）-（9-6）=13.

主要是因为这个方法，没有能力在迭代到9的时候，找出前面最大的a[i]+i,从而错失了最佳答案。

代码

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& a) {
        int left=a[0],ans=-1e9;//ans初始化为一个很小的数 防止初始化大于最佳答案 从而发生掩盖的问题
        for(int i=1;i<a.size();i++){
            ans=max(ans,left+a[i]-i);
            left=max(left,a[i]+i);
        }
        return ans;
    }
    
};
           

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& a) {
        int right=a[a.size()-1]-a.size()+1,ans=-1e9;
        for(int i=a.size()-2;i<a.size();i--){
            ans=max(ans,right+a[i]+i);
            right=max(right,a[i]-i);
        }
        return ans;
    }
    
};
           

三元素比较的算法代码（没有AC）

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& a) {
        int left=a[0],right=a[1]-1;
        int l=0,r=1;
        //l和r的设置是方便计算a[i]-i变成a[i]+i后的数值
        for(int i=2;i<a.size();i++){
            int tmp1=left+right;
            int tmp2=left+a[i]-i;
            int tmp3=right+2*r+a[i]-i;
            //三数值比较
            int tmp=max(tmp1,max(tmp2,tmp3));
            if(tmp==tmp2){
                r=i;
                right=a[i]-i;
            }
            else if(tmp==tmp3){
                left=right+2*r;
                right=a[i]-i;
                l=r;
                r=i;
            }
			//tmp==tmp1就不用改变left和right
        }
        return left+right;

    }
    
};