[LeetCode] 1014. Best Sightseeing Pair

[grandyang]

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:

1. 2 <= A.length <= 50000
2. 1 <= 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 同步地址:

#1014

参考资料：

https://leetcode.com/problems/best-sightseeing-pair/

https://leetcode.com/problems/best-sightseeing-pair/discuss/260884/C%2B%2B-O(n)-best-time-to-buy-and-sell-stock

https://leetcode.com/problems/best-sightseeing-pair/discuss/260850/JavaC%2B%2BPython-One-Pass-O(1)-space

LeetCode All in One 题目讲解汇总(持续更新中...)