力扣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;

    }
    
};