# Best Sightseeing Pair
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/best-sightseeing-pair)
Canonical: https://scaleengineer.com/dsa/problems/best-sightseeing-pair
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## Problem
You are given an integer array `values` where values\[i\] represents the value of the `ith` sightseeing spot. Two sightseeing spots `i` and `j` have a **distance** `j - i` between them.

The score of a pair (`i < j`) of sightseeing spots is `values[i] + values[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:** values = [8,1,5,2,6]
**Output:** 11
**Explanation:** i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

**Example 2:**

**Input:** values = [1,2]
**Output:** 2

**Constraints:**

* `2 <= values.length <= 5 * 104`
* `1 <= values[i] <= 1000`

# Approaches
## Brute Force
This approach involves checking every possible pair of sightseeing spots `(i, j)` where `i < j`. For each pair, it calculates the score and keeps track of the maximum score found so far. While simple to conceptualize, it is not efficient enough for the given constraints.
**Time:** O(N^2), where N is the number of sightseeing spots. The nested loops result in a quadratic number of score calculations, making it too slow for large N. · **Space:** O(1), as it only uses a few variables to store the maximum score and loop indices, requiring constant extra space.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small input sizes.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for large inputs, such as the ones specified in the problem constraints.
### Explanation
The brute-force method directly translates the problem statement into code. We use two nested loops to generate all valid pairs of indices `(i, j)` such that `i` is always less than `j`.

The outer loop selects the first sightseeing spot `i`, and the inner loop selects the second spot `j` from the remaining spots to the right. For each pair, we compute the score using the formula `values[i] + values[j] + i - j`. A variable, `maxScore`, is maintained throughout the process and is updated whenever a newly calculated score is higher than the current `maxScore`. After iterating through all possible pairs, `maxScore` will hold the highest possible score.

```java
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int n = values.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentScore = values[i] + values[j] + i - j;
                maxScore = Math.max(maxScore, currentScore);
            }
        }
        return maxScore;
    }
}
```
### Algorithm
- Initialize a variable `maxScore` to a very small number (or 0, since scores are positive).
- Use a nested loop structure. The outer loop iterates with index `i` from `0` to `n-2`.
- The inner loop iterates with index `j` from `i+1` to `n-1`.
- Inside the inner loop, calculate the score for the pair `(i, j)`: `currentScore = values[i] + values[j] + i - j`.
- Update `maxScore` if `currentScore` is greater: `maxScore = max(maxScore, currentScore)`.
- After both loops complete, return `maxScore`.

## Single Pass with Optimization
A more efficient approach is to use a single pass through the array. By rearranging the score formula `values[i] + values[j] + i - j` into `(values[i] + i) + (values[j] - j)`, we can see that for each spot `j`, we want to find the best possible spot `i` (where `i < j`) that maximizes the `values[i] + i` part. We can keep track of this maximum value as we iterate through the array.
**Time:** O(N), where N is the number of sightseeing spots. This is because we iterate through the array only once. · **Space:** O(1), as it only requires a few variables to store the running maximums, independent of the input size.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Uses constant extra space, making it memory-efficient.
**Cons:** The logic is less intuitive than the brute-force approach and requires an algebraic manipulation of the score formula to see the optimization.
### Explanation
The key to this optimization is recognizing that the score formula can be split into two independent parts: one that depends only on `i` and one that depends only on `j`. The score for a pair `(i, j)` is `(values[i] + i) + (values[j] - j)`.

As we iterate through the array with an index `j`, our goal is to find the maximum possible score. This score is achieved by pairing the current `j`'s contribution, `values[j] - j`, with the maximum possible contribution from a previous `i` (where `i < j`), which is `max(values[i] + i)`. 

We can maintain a variable, let's call it `max_i_part`, that stores the maximum value of `values[i] + i` encountered so far. We iterate from `j = 1` to the end of the array. In each step, we calculate a potential score using the current `j` and the `max_i_part` we've maintained. Then, we update `max_i_part` with the value from the current index `j` (`values[j] + j`) if it's larger, making it available for future calculations. This allows us to find the overall maximum score in just one pass.

```java
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        // max_i_part represents the maximum value of (values[i] + i) seen so far.
        // Initialize it with the value for the first element (i=0).
        int max_i_part = values[0] + 0;
        int maxScore = 0;

        // Iterate from the second element (j=1) to the end.
        for (int j = 1; j < values.length; j++) {
            // For the current j, the best score is pairing it with the best i (i < j).
            // The score is (values[i] + i) + (values[j] - j).
            // We use max_i_part for the (values[i] + i) part.
            maxScore = Math.max(maxScore, max_i_part + values[j] - j);
            
            // After using j to calculate a score, update max_i_part.
            // The current element j can be the 'i' for a future pair.
            max_i_part = Math.max(max_i_part, values[j] + j);
        }
        
        return maxScore;
    }
}
```
### Algorithm
- Rearrange the score formula: `score = (values[i] + i) + (values[j] - j)`.
- Initialize `maxScore = 0`.
- Initialize a variable `max_i_part = values[0] + 0`. This variable will track the maximum value of `values[i] + i` seen so far.
- Iterate through the array with index `j` from `1` to `n-1`.
- For each `j`, calculate the potential score with the best `i` found so far: `currentScore = max_i_part + values[j] - j`.
- Update the overall maximum score: `maxScore = max(maxScore, currentScore)`.
- Update `max_i_part` for future iterations: `max_i_part = max(max_i_part, values[j] + j)`.
- Return `maxScore` after the loop.

# Solutions
### Java

```java
class Solution {
public
  int maxScoreSightseeingPair(int[] values) {
    int ans = 0, mx = values[0];
    for (int j = 1; j < values.length; ++j) {
      ans = Math.max(ans, values[j] - j + mx);
      mx = Math.max(mx, values[j] + j);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxScoreSightseeingPair(vector<int> &values) {
    int ans = 0, mx = values[0];
    for (int j = 1; j < values.size(); ++j) {
      ans = max(ans, values[j] - j + mx);
      mx = max(mx, values[j] + j);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int: ans, mx = 0, values[0] for j in range(1, len(values)): ans = max(ans, values[j] - j + mx) mx = max(mx, values[j] + j) return ans

```