Best Easy Solution | O(n) | prefixMax needed only!! | 8 min vid solution
Vid SolutionIntuition
Sightseeing Pair: A sightseeing pair consists of two indices i and j in the values array, where i < j.
Score: The score of a sightseeing p
# Vid Solution
https://youtu.be/-cYzuDbn1ls

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- Sightseeing Pair: A sightseeing pair consists of two indices i and j in the values array, where i < j.
- Score: The score of a sightseeing pair is calculated as values[i] + values[j] + i - j.
- Key Observation: To maximize the score, we need to find a balance between selecting a high values[i] and a high values[j], while also considering the i - j term which can significantly impact the score.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Initialization:

- preFixMax: Stores the maximum value of values[i] + i encountered so far. Initially, it's set to values[0].
- maxScore: Stores the maximum score found so far. Initially, it's set to 0.
2. Iteration:

- Iterate through the values array starting from index 1.
- For each index j:
- Calculate the potential score of the current pair: values[j] - j + preFixMax.
- Update maxScore if the potential score is greater than the current maxScore.
- Update preFixMax with the maximum value between the current preFixMax and values[j] + j. This step is crucial as it ensures that we always consider the best possible values[i] for the subsequent pairs.
3. Return:

- After iterating through the entire array, return the maxScore.

# Complexity
- Time complexity:O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {

        int preFixMax = values[0];
        int maxScore = 0;

        int n = values.size();

        for(int j=1;j<n;j++){

            maxScore = max(maxScore,preFixMax + values[j]-j);
            preFixMax = max(preFixMax, values[j]+j);
        }
        

        return maxScore;
    }
};
```
['C++']