Beats 100%✅✅ || Easy to understand solution
IntuitionThe problem can be divided into two parts:
Maximizing values[i] + i for the left part.
Maximizing values[j] - j for the right part.
The best sightseein
# Intuition
The problem can be divided into two parts:
1. Maximizing `values[i] + i` for the left part.
2. Maximizing `values[j] - j` for the right part.

The best sightseeing pair can be determined by combining the maximum values from both parts.

# Approach
1. Precompute the `leftMax` array, where `leftMax[i]` stores the maximum value of `values[k] + k` for all `k <= i`.
2. Precompute the `rightMax` array, where `rightMax[i]` stores the maximum value of `values[k] - k` for all `k >= i`.
3. Iterate through the array to find the maximum sum of `leftMax[i-1] + rightMax[i]` for all valid `i`.

# Complexity
- Time complexity: $$O(n)$$, where `n` is the size of the array, as we iterate over the array a constant number of times.
- Space complexity: $$O(n)$$, for storing the `leftMax` and `rightMax` arrays.

# Code
```cpp []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size();
        vector<int> leftMax(n), rightMax(n);

        // Compute leftMax array
        leftMax[0] = values[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i - 1], values[i] + i);
        }

        // Compute rightMax array
        rightMax[n - 1] = values[n - 1] - (n - 1);
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = max(rightMax[i + 1], values[i] - i);
        }

        // Compute the maximum score
        int maxi = 0;
        for (int i = 1; i < n; i++) {
            maxi = max(maxi, leftMax[i - 1] + rightMax[i]);
        }

        return maxi;
    }
};
```
``` Java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int n = values.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // Compute leftMax array
        leftMax[0] = values[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], values[i] + i);
        }

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

        // Compute the maximum score
        int maxi = 0;
        for (int i = 1; i < n; i++) {
            maxi = Math.max(maxi, leftMax[i - 1] + rightMax[i]);
        }

        return maxi;
    }
}
```
```JavaScript []
/**
 * @param {number[]} values
 * @return {number}
 */
var maxScoreSightseeingPair = function(values) {
    const n = values.length;
    const leftMax = Array(n).fill(0);
    const rightMax = Array(n).fill(0);

    // Compute leftMax array
    leftMax[0] = values[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], values[i] + i);
    }

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

    // Compute the maximum score
    let maxi = 0;
    for (let i = 1; i < n; i++) {
        maxi = Math.max(maxi, leftMax[i - 1] + rightMax[i]);
    }

    return maxi;
};

```
```Python []
class Solution(object):
    def maxScoreSightseeingPair(self, values):
        """
        :type values: List[int]
        :rtype: int
        """
        n = len(values)
        left_max = [0] * n
        right_max = [0] * n

        # Compute left_max array
        left_max[0] = values[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], values[i] + i)

        # Compute right_max array
        right_max[n - 1] = values[n - 1] - (n - 1)
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], values[i] - i)

        # Compute the maximum score
        maxi = 0
        for i in range(1, n):
            maxi = max(maxi, left_max[i - 1] + right_max[i])

        return maxi

```
['Python', 'C++', 'Java', 'Python3', 'JavaScript']