0 ms || Beats 100 % || One pass Solution || Space optimized DP Solution || Beginner Friendly
Problem Understanding:Given an integer array values where values[i] represents the value of the ith sightseeing spot, we need to find the maximum score of a pai
![image.png](https://assets.leetcode.com/users/images/0626981d-4859-48ce-9754-eb12a4d59a3a_1735281516.9131582.png)

# Problem Understanding:
<!-- Describe your first thoughts on how to solve this problem. -->
Given an integer array values where values[i] represents the value of the ith sightseeing spot, we need to find the maximum score of a pair of sightseeing spots. The score of a pair (i < j) is defined as:
            **$$score(i,j)=values[i]+values[j]+i−j$$**
Our goal is to find the pair (i, j) that maximizes the score, where $$i < j.$$
# Approach
<!-- Describe your approach to solving the problem. -->
**Key Insight:**
The score formula values[i] + values[j] + i - j can be split into two components:
    **$$score(i,j)=(values[i]+i)+(values[j]−j)$$**
This insight allows us to think of the problem in two parts:

1. Left part: We need to keep track of the best possible value of $$values[i] + i$$ as we iterate through the array.
2. Right part: For each j, we calculate the score by combining the best $$values[i] + i$$ seen so far with $$values[j] - j$$.

The solution involves iterating through the array while maintaining the maximum score we can achieve by selecting a j and using the best i (where i < j).

Approach:
1. **Initialize:** Start with the first element, where left = values[0] (since the first spot doesn't have any prior spot).
2. **Iterate over the array:** For each spot j starting from index 1, calculate the score using the current left (which holds the best values[i] + i up to j-1).
3. **Update:** After calculating the score for the current j, update left to reflect the best value of values[j] + j for future comparisons.

This way, we can calculate the score for all valid pairs (i, j) in one linear scan.


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

- Space complexity: $$O(1)$$ -> no extra space required expect 3 variables
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Example: 
```
values = [8, 1, 5, 2, 6]
```
1. Start with $$left = values[0] = 8$$, $$maxi = -INF$$.
2. For j = 1, calculate $$score = left + values[1] - 1 = 8 + 1 - 1 = 8$$, so $$maxi = 8$$. Update $$left = max(left, values[1] + 1) = 2$$.
3. For j = 2, calculate $$score = left + values[2] - 2 = 2 + 5 - 2 = 5$$, so $$maxi = 8$$. Update $$left = max(left, values[2] + 2) = 7$$.
4. For j = 3, calculate $$score = left + values[3] - 3 = 7 + 2 - 3 = 6$$, so $$maxi = 8$$. Update $$left = max(left, values[3] + 3) = 5$$.
5. For j = 4, calculate $$score = left + values[4] - 4 = 5 + 6 - 4 = 7$$,   so $$maxi = 11$$. Final $$maxi = 11$$.

# Code
```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int n = values.length;
        int maxi = Integer.MIN_VALUE;  // To store the maximum score
        int left = values[0];  // Initialize left part as values[0] + 0

        // Iterate through the array starting from index 1
        for (int j = 1; j < n; j++) {
            // Update maxi by considering the score for current pair (left, j)
            maxi = Math.max(maxi, left + values[j] - j);

            // Update left for future pairs: values[i] + i, where i < j
            left = Math.max(left, values[j] + j);
        }

        return maxi;
    }
}

```
```python []
class Solution:
    def maxScoreSightseeingPair(self, values):
        n = len(values)
        maxi = float('-inf')  # To store the maximum score
        left = values[0]  # Initialize left part as values[0] + 0

        # Iterate through the array starting from index 1
        for j in range(1, n):
            # Update maxi by considering the score for current pair (left, j)
            maxi = max(maxi, left + values[j] - j)

            # Update left for future pairs: values[i] + i, where i < j
            left = max(left, values[j] + j)

        return maxi

```
```cpp []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size();
        int maxi = INT_MIN;  // To store the maximum score
        int left = values[0]; // Initialize left part as values[0] + 0

        // Iterate through the array starting from index 1
        for (int j = 1; j < n; j++) {
            // Update maxi by considering the score for current pair (left, j)
            maxi = max(maxi, left + values[j] - j);

            // Update left for future pairs: values[i] + i, where i < j
            left = max(left, values[j] + j);
        }

        return maxi;
    }
};

```
['Array', 'Dynamic Programming', 'Greedy', 'C++', 'Java', 'Python3']