1014.Best Sightseeing Pair

Tags: Medium Array

Links: https://leetcode.com/problems/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

---

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = A.size();
        int res = 0;
        int maxVal = A[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (A[i] + maxVal - 1 > res) {
                res = A[i] + maxVal - 1;
            }
            maxVal = max(maxVal - 1, A[i]);
        }

        return res;
    }
};

首先如果这道题暴力求解，那么方法是从数组第一个元素开始，依次去计算剩余元素A[j] + i - j的最大值，时间复杂度是$O(n^2)$，一看数据范围肯定超时，所以对去寻找A[j] + i - j的最大值部分进行优化，我们来看一下整体的寻找过程：

下标	0	1	2	3	4
数值	8	1	5	2	6
距离i - j		-1	-2	-3	-4
			-1	-2	-3
				-1	-2
					-1

我们从数组的最后两个元素开始遍历，将每次取到最大值的点加粗表示，观察每次取到最大值的规律：

下标	0	1	2	3	4	观光最大值
数值	8	1	5	2	6
A[j] + i - j	8	0	3	-1	2	11
		1	4	0	3	5
			5	1	4	9
				2	5	7

从数组的最后两个数开始寻找最优值，初始以下标3作为i，那么j-i是-1，A[j]+i-j的结果是5，最优值是7；然后位置前移，此时下标2作为i，为了让总和最大，肯定要从i后面里选择A[j] + i - j最大的值，也就是让下标j = 4，而这个4恰好是上一轮的最大值5-1的结果，如果此时规律还不明显，就再看一个；位置前移，下标i = 1，上一轮的最大值是下标2对应的5。

可以发现，下标i的位置每次前移一个位置，其身后的数字A[j] + i - j都是上一轮的A[j] + i - j减去1，如果在某一个j使得A[j] + i - j取到最大值，除非i超过这个最大值，不然i后面其他的数字在任何一轮都不会超过j对应的数字，因为i后面的数字都会同时减去1，所以只需要维护一个A[j] + i - j局部最大值即可。

这样只需遍历一边数组，时间复杂度$O(n)$，空间复杂度$O(1)$。