✅Easy to Understand | 100% | Java | C++ | Python | Detailed Video Explanation🔥
IntuitionThe problem involves maximizing the score of a sightseeing pair, which is defined as values[i] + values[j] + i - j. By breaking this down, we can split
# Intuition
The problem involves maximizing the score of a sightseeing pair, which is defined as `values[i] + values[j] + i - j`. By breaking this down, we can split it into two components:
1. `(values[i] + i)`: A fixed contribution from the left side.
2. `(values[j] - j)`: A dynamic contribution from the right side as we iterate.

The goal is to efficiently keep track of the maximum possible `(values[i] + i)` encountered so far and combine it with the current `(values[j] - j)` to calculate the maximum score in \(O(n)\) time.

# Approach
1. Start by initializing a variable `first` to represent the maximum value of `(values[i] + i)` seen so far, starting with the first element.
2. Iterate through the array starting from index `1`.
   - For each index `j`, compute `second = values[j] - j`.
   - Update the result by checking if the sum of `first + second` is greater than the current maximum score.
   - Update `first` to include the current contribution `(values[j] + j)` for potential use in future iterations.
3. Return the maximum score after processing all elements.

This approach ensures that we only iterate through the array once, keeping the computation efficient.

# Complexity
- Time complexity:  
  $$O(n)$$  
  We traverse the array once, performing constant-time operations at each step.

- Space complexity:  
  $$O(1)$$  
  Only a few variables are used for computation, with no additional data structures.


# Code
```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        // Initialize 'first' to represent the maximum value of (values[i] + i) seen so far
        int first = values[0] + 0;

        // Get the size of the input array
        int n = values.length;

        // Initialize the answer to the minimum possible value
        int ans = Integer.MIN_VALUE;

        // Iterate through the array starting from index 1
        for(int j = 1; j < n; j++) {
            // Calculate 'second' as (values[j] - j) for the current index
            int second = values[j] - j;

            // Update the maximum score by considering the current 'first' and 'second'
            ans = Math.max(ans, first + second);

            // Update 'first' to include the current element's contribution to (values[i] + i)
            first = Math.max(first, values[j] + j);
        }

        // Return the maximum score of a sightseeing pair
        return ans;
    }
}

```
```c++ []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        // Initialize 'first' to represent the maximum value of (values[i] + i) seen so far
        int first = values[0] + 0;

        // Initialize the answer to the minimum possible value
        int ans = INT_MIN;

        // Iterate through the array starting from index 1
        for (int j = 1; j < values.size(); j++) {
            // Calculate 'second' as (values[j] - j) for the current index
            int second = values[j] - j;

            // Update the maximum score by considering the current 'first' and 'second'
            ans = max(ans, first + second);

            // Update 'first' to include the current element's contribution to (values[i] + i)
            first = max(first, values[j] + j);
        }

        // Return the maximum score of a sightseeing pair
        return ans;
    }
};

```
```python []
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        # Initialize 'first' to represent the maximum value of (values[i] + i) seen so far
        first = values[0] + 0

        # Initialize the answer to the minimum possible value
        ans = float('-inf')

        # Iterate through the array starting from index 1
        for j in range(1, len(values)):
            # Calculate 'second' as (values[j] - j) for the current index
            second = values[j] - j

            # Update the maximum score by considering the current 'first' and 'second'
            ans = max(ans, first + second)

            # Update 'first' to include the current element's contribution to (values[i] + i)
            first = max(first, values[j] + j)

        # Return the maximum score of a sightseeing pair
        return ans

```




LeetCode 1014 Best Sightseeing Pair | Array | DP | Asked in Google
https://youtu.be/icOKLdBEtFM
['Array', 'Dynamic Programming', 'Python', 'C++', 'Java']