Best Sightseeing Pair

LeetCode

第28天。

今天的题目是Best Sightseeing Pair:

这道题的关键就是什么时候移动 i 这个下标，我们观察一下这个公式：A[i] + A[j] + i - j，转化一下就成了(A[i] + i) + (A[j] - j)，因此如果存在两个i，即i1和i2的话，当A[i1] + i1 > A[i2] + i2成立时，我们就可以用 i2去替代原来的i1。至于j的话，我们只需要从头到尾遍历一遍即可，同时在穷举j的时候，可以顺便穷举出i：

1
2
3
4
5
6
7
8
9
10
11
12
int maxScoreSightseeingPair(vector<int>& A) {
    int size =  A.size();
    int res = 0;
    if (size == 0) return res;
    
    for(int i = 0, j = 1;j < size; j++) {
        res = max(res, A[i] + A[j] + i - j);
        if (A[j] + j > A[i] + i) i = j;
    }
    
    return res;
}

我们把式子重写成A[j] + (A[i] + i - j)，随着j++，i - j会减一，如果不改变 i的话，(A[i] + i - j)相比于之前就只是减一而已，如果要改变的话，A[i] + i - j = A[j] - 1,则我们可以将循环简化成：

1
2
3
4
5
6
7
8
9
10
11
12
int maxScoreSightseeingPair(vector<int>& A) {
    int size =  A.size();
    int res = 0;
    if (size == 0) return res;
    int cur = 0;
    for(int j = 0;j < size; j++) {
        res = max(res, cur + A[j]);
        cur = max(cur, A[j]) - 1;
    }
    
    return res;
}