# Leetcode 1014. Best Sightseeing Pair
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/best-sightseeing-pair/submissions/ 。

想法 :

因為i<j，所以要找先前最好的i，也就是持續更新values[i]+i為最大值。
接著往後找values[j]-j就好。
那，會不會存在被更新掉的values[i]+i會比更新後的值來得大?
A:不會，因為j固定的話那只考慮values[i]+i而已。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int l = values.size(), prevIndex = 0, best = 0;
        
        for(int i=1 ; i<l ; i++){
            if(values[prevIndex] + prevIndex + values[i] - i > best){
                best = values[prevIndex] + prevIndex + values[i] - i;
            }
            if(values[i] + i > values[prevIndex] + prevIndex){
                prevIndex = i;
            }
        }
        
        return best;
    }
};