Leetcode 1014. Best Sightseeing Pair

Problem Explanation:

The problem's main task is to calculate the maximum score that can be calculated from the array of positive integers given, where each integer represents the value of a sightseeing spot. The score is the sum of the values of two sightseeing spots i and j (where i < j), minus the distance between them, which is (j - i).

A naive way would be to use two loops and try every possible pair of i and j, calculate the score for each pair, and update the maximum score. However, this approach would take O(N^2) time complexity, and is not efficient.

The more efficient approach to this problem is to use a single pass approach, where we keep track of the highest score so far, and the best previous value we have encountered. Each time we find a new value, we calculate the potential score with the best previous value and update the highest score if necessary. Then we update the best previous value.

The time complexity of this approach is O(N), where N is the number of elements in the array.

Let's take an example:

Input: [8,1,5,2,6]

• We start with ans = 0, bestPrev = 0

• For the first value 8:
  ans = max(0, 8+0) = 8
  bestPrev = max(0, 8) - 1 = 7

• For the next value 1:
  ans = max(8, 1+7) = 8
  bestPrev = max(7, 1) - 1 = 6

• For the next value 5:
  ans = max(8, 5+6) = 11
  bestPrev = max(6, 5) - 1 = 5
  . .

The process goes on like this until we have covered all the values in the array. In the end, 'ans' will have the maximum score of a pair of sightseeing spots.

Solution:

Python

1
2python
3class Solution:
4    def maxScoreSightseeingPair(self, A):
5        ans = 0
6        bestPrev = 0
7        for value in A:
8            ans = max(ans, value + bestPrev)
9            bestPrev = max(bestPrev, value) - 1
10        return ans

Java

1
2java
3public class Solution {
4    public int maxScoreSightseeingPair(int[] A) {
5        int ans = 0;
6        int bestPrev = 0;
7        for (int value : A) {
8            ans = Math.max(ans, value + bestPrev);
9            bestPrev = Math.max(bestPrev, value) - 1;
10        }
11        return ans;
12    }
13}

JavaScript

1
2javascript
3class Solution {
4    maxScoreSightseeingPair(A) {
5        let ans = 0;
6        let bestPrev = 0;
7        for (let value of A) {
8            ans = Math.max(ans, value + bestPrev);
9            bestPrev = Math.max(bestPrev, value) - 1;
10        }
11        return ans;
12    }
13}

C++

1
2cpp
3class Solution {
4public:
5    int maxScoreSightseeingPair(vector<int>& A) {
6        int ans = 0;
7        int bestPrev = 0;
8        for (int value : A) {
9            ans = max(ans, value + bestPrev);
10            bestPrev = max(bestPrev, value) - 1;
11        }
12        return ans;
13    }
14};

C#

1
2csharp
3public class Solution {
4    public int MaxScoreSightseeingPair(int[] A) {
5        int ans = 0;
6        int bestPrev = 0;
7        for (int i = 0; i < A.Length; i++) {
8            ans = Math.Max(ans, A[i] + bestPrev);
9            bestPrev = Math.Max(bestPrev, A[i]) - 1;
10        }
11        return ans;
12    }
13}

In the solutions above, we iterate through the array, maintaining and updating the maximum score and the number that would give the highest score when paired with some other number down the line.

All these solutions use the same approach, updating ans with the highest score and bestPrev with the highest score that certain number could produce. But with each iteration, we subtract one from bestPrev because moving along the array costs 1 point according to the problem constraints: score = A[i] + A[j] - (j - i).

By maintaining bestPrev, we effectively store the highest potential score a subsequent number can add when paired with a previous number. It's important to subtract one from bestPrev every time the loop reruns because the distance penalty increases as we look further to the right in the array.

In essence, we are using a greedy strategy here, greedily updating our max score and max individual score as we progress through the array, ensuring that at every point we could always form a pair that yields the largest possible score. This way, we could solve the problem in a linear O(N) time complexity, iterating through the array once, instead of a quadratic O(N^2) time complexity if we were to pair every number with every other number.