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

Analysis

By using brute-force, it will cause TLE.

We can rarrange the equation into A[i] + i + A[j] - j, where i < j. So that we just need to make sure A[i] + i is the maximum and since it's always on the left side of j and A[j], we can "lazy" update its value when we process to the right.

Time: $O(n)$

Space: $O(1)$

Code

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int res = 0, n = A.size(), mx = 0; // mx = A[i] + i
        for (int i = 0; i < n; ++i) {
            res = max(res, mx + A[i] - i);
            mx = max(mx, A[i] + i);
        }
        return res;
    }
};

---

Last update: March 31, 2022