1014. Best Sightseeing Pair

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation