Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.
The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.
Return the maximum score of a pair of sightseeing spots.
Example 1:
Input: [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, `A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11`
Note:
2 <= A.length <= 500001 <= A[i] <= 1000
这道题给了一个正整数的数组A，定义了一种两个数字对儿的记分方式，为 A[i] + A[j] + i - j，现在让找出最大的那组的分数。博主首先尝试了一下暴力搜索法，遍历所有的两个数的组合，计算得分，毫不意外的超时了，虽然只是一道 Medium 的题，仍然要给予 OJ 足够的尊重。那么来考虑如何优化一下，利用加法的分配律，可以得到 A[i] + i + A[j] - j，为了使这个表达式最大化，A[i] + i 自然是越大越好，这里可以使用一个变量 mx 来记录之前出现过的 A[i] + i 的最大值，则当前的数字就可以当作数对儿中的另一个数字，其减去当前坐标值再加上 mx 就可以更新结果 res 了，参见代码如下：
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& A) {
int res = 0, n = A.size(), mx = 0;
for (int i = 0; i < n; ++i) {
res = max(res, mx + A[i] - i);
mx = max(mx, A[i] + i);
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1014
参考资料：
https://leetcode.com/problems/best-sightseeing-pair/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
