Simple & Clean Solution | ✅ Beats 100% | 💡 O(n) Approach | C++ | Java | Python | JS
⬆️Upvote if it helps ⬆️Connect with me on Linkedin [Bijoy Sing]IntuitionThe problem revolves around maximizing the score of two sightseeing spots by efficiently
# ⬆️Upvote if it helps ⬆️

---

## Connect with me on Linkedin [Bijoy Sing]

---

```cpp []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0;
        int Prev = values[0];

        for (int j = 1; j < values.size(); j++) {
            ans = max(ans, Prev + values[j] - j);
            Prev = max(Prev, values[j] + j);
        }

        return ans;
    }
};
```

```python []
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        ans = 0
        Prev = values[0]

        for j in range(1, len(values)):
            ans = max(ans, Prev + values[j] - j)
            Prev = max(Prev, values[j] + j)

        return ans
```

```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0;
        int Prev = values[0];

        for (int j = 1; j < values.length; j++) {
            ans = Math.max(ans, Prev + values[j] - j);
            Prev = Math.max(Prev, values[j] + j);
        }

        return ans;
    }
}
```

```javascript []
class Solution {
    maxScoreSightseeingPair(values) {
        let ans = 0;
        let Prev = values[0];

        for (let j = 1; j < values.length; j++) {
            ans = Math.max(ans, Prev + values[j] - j);
            Prev = Math.max(Prev, values[j] + j);
        }

        return ans;
    }
}
```

---

# Intuition
The problem revolves around maximizing the score of two sightseeing spots by efficiently managing the difference between their indices and maximizing the sum of their values. 

# Approach
- Maintain a running maximum (`Prev`) of \( values[i] + i \), which represents the best value of the first spot up to the current index.
- Iterate through the array and for each index \(j\), compute the score of the pair \(i, j\) using \( Prev + values[j] - j \).
- Update the maximum score (`ans`) and `Prev` as you progress.

# Complexity
- Time complexity: 
  $$O(n)$$, where \(n\) is the length of the `values` array, as we iterate through the array once.

- Space complexity: 
  $$O(1)$$, since no extra space is used apart from a few variables.

### *If you have any questions or need further clarification, feel free to drop a comment! 😊*
['Array', 'Sliding Window', 'Suffix Array', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']