Code & Fun

第28天。

今天的题目是Best Sightseeing Pair:

这道题的关键就是什么时候移动 i 这个下标,我们观察一下这个公式:A[i] + A[j] + i - j,转化一下就成了(A[i] + i) + (A[j] - j),因此如果存在两个i,即i1i2的话,当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;
}

本文首发于Code & Fun