Only Suffix Array  O(n) 100% Beats
🌟 IntuitionTo maximize the sightseeing pair score, we need to recognize the key components in the formula:score = values[i] + values[j] + i - jWe can rearrange
# 🌟 Intuition
To maximize the sightseeing pair score, we need to recognize the key components in the formula:

score = values[i] + values[j] + i - j

We can rearrange this to:

score = (values[i] + i) + (values[j] - j)

This shows that:
- The first part, `values[i] + i`, is the **left part** of the score.
- The second part, `values[j] - j`, is the **right part** of the score.

### 🧠 Key Insight:
We can **precompute** the **right part** (`values[j] - j`) for all `j` and use this precomputed information when calculating the score for any `i`. This allows us to maximize the score efficiently without checking every pair.

---

# 🚀 Approach
### 1. **Suffix Array** 📊:
To efficiently track the maximum of `values[j] - j` for all possible `j > i`, we use a **suffix array**:
- This array holds the maximum value of `values[j] - j` for each index `j` starting from the end of the array.

### 2. **Iterate and Calculate** 🔄:
For each index `i`, calculate the score using the precomputed values from the suffix array:
- For each `i`, the score is the sum of `values[i] + i` (the left part) and `suffixMax[i + 1]` (the right part).

By combining these two parts, we can find the maximum score for the sightseeing pair.

### 3. **Edge Cases** ⚠️:
Handle cases with fewer than 2 elements by returning the score directly for the pair `(values[0], values[1])`.

---

# 🧠 Complexity
### Time Complexity ⏱️:
- **O(n)**: We make two passes through the array:  
  1. One pass to compute the `suffixMax` array.  
  2. Another pass to calculate the maximum score.

### Space Complexity 💾:
- **O(n)**: We store the `suffixMax` array to keep track of the maximum values of `values[j] - j`.
![Screenshot 2024-12-27 073048.png](https://assets.leetcode.com/users/images/19bcfc6a-e667-4bd5-a922-704dddaba2e2_1735264901.7680144.png)

---

# 💻 Code

```cpp []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size();
        if (n < 2) return values[0] + values[1] + 0 - 1; 
        vector<int> suffixMax(n);
        suffixMax[n - 1] = values[n - 1] - (n - 1);
        for (int i = n - 2; i >= 0; i--) {
            suffixMax[i] = max(suffixMax[i + 1], values[i] - i);
        }
        int maxScore = INT_MIN;
        for (int i = 0; i < n - 1; i++) {
            maxScore = max(maxScore, values[i] + i + suffixMax[i + 1]);
        }

        return maxScore;
    }
};
```
```Python3 []
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        n = len(values)
        suffixMax = [0] * n
        suffixMax[n - 1] = values[n - 1] - (n - 1)

        for i in range(n - 2, -1, -1):
            suffixMax[i] = max(suffixMax[i + 1], values[i] - i)

        maxScore = float('-inf')

        for i in range(n - 1):
            maxScore = max(maxScore, values[i] + i + suffixMax[i + 1])

        return maxScore
```
```Java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int n = values.length;
        int[] suffixMax = new int[n];
        suffixMax[n - 1] = values[n - 1] - (n - 1);

        for (int i = n - 2; i >= 0; i--) {
            suffixMax[i] = Math.max(suffixMax[i + 1], values[i] - i);
        }

        int maxScore = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; i++) {
            maxScore = Math.max(maxScore, values[i] + i + suffixMax[i + 1]);
        }

        return maxScore;
    }
}
```
```C []
int maxScoreSightseeingPair(int* values, int valuesSize) {
    int* suffixMax = (int*)malloc(valuesSize * sizeof(int));
    suffixMax[valuesSize - 1] = values[valuesSize - 1] - (valuesSize - 1);

    for (int i = valuesSize - 2; i >= 0; i--) {
        suffixMax[i] = fmax(suffixMax[i + 1], values[i] - i);
    }

    int maxScore = INT_MIN;

    for (int i = 0; i < valuesSize - 1; i++) {
        maxScore = fmax(maxScore, values[i] + i + suffixMax[i + 1]);
    }

    free(suffixMax);
    return maxScore;
}
```
```C# []
public class Solution {
    public int MaxScoreSightseeingPair(int[] values) {
        int n = values.Length;
        int[] suffixMax = new int[n];
        suffixMax[n - 1] = values[n - 1] - (n - 1);

        for (int i = n - 2; i >= 0; i--) {
            suffixMax[i] = Math.Max(suffixMax[i + 1], values[i] - i);
        }

        int maxScore = int.MinValue;

        for (int i = 0; i < n - 1; i++) {
            maxScore = Math.Max(maxScore, values[i] + i + suffixMax[i + 1]);
        }

        return maxScore;
    }
}
```
```JavaScript []
var maxScoreSightseeingPair = function(values) {
    let n = values.length;
    let suffixMax = new Array(n);
    suffixMax[n - 1] = values[n - 1] - (n - 1);

    for (let i = n - 2; i >= 0; i--) {
        suffixMax[i] = Math.max(suffixMax[i + 1], values[i] - i);
    }

    let maxScore = -Infinity;

    for (let i = 0; i < n - 1; i++) {
        maxScore = Math.max(maxScore, values[i] + i + suffixMax[i + 1]);
    }

    return maxScore;
};
```
```Ruby []
# @param {Integer[]} values
# @return {Integer}
def max_score_sightseeing_pair(values)
    n = values.length
    suffix_max = Array.new(n)
    suffix_max[n - 1] = values[n - 1] - (n - 1)

    (n - 2).downto(0) do |i|
        suffix_max[i] = [suffix_max[i + 1], values[i] - i].max
    end

    max_score = -Float::INFINITY

    (0...n - 1).each do |i|
        max_score = [max_score, values[i] + i + suffix_max[i + 1]].max
    end

    return max_score
end
```
['C', 'C++', 'Java', 'Python3', 'Ruby', 'JavaScript', 'C#']