Python | Greedy Algorithm Pattern
see the Successfully Accepted SubmissionCodeExplanationInitialization:
Start with max_score = 0 to track the highest score.
Use max_i_value to store the maximum
[see the Successfully Accepted Submission](https://leetcode.com/problems/best-sightseeing-pair/submissions/1489297050/?envType=daily-question&envId=2024-12-27)

# Code
```python3 []
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        # Initialize variables
        max_score = 0
        max_i_value = values[0] + 0  # This is values[i] + i for the first element

        # Iterate through the array starting from the second element
        for j in range(1, len(values)):
            # Calculate the score for the current pair (i, j)
            max_score = max(max_score, max_i_value + values[j] - j)

            # Update max_i_value to include the current index
            max_i_value = max(max_i_value, values[j] + j)

        return max_score

```

### Explanation

#### Initialization:

- Start with `max_score = 0` to track the highest score.
- Use `max_i_value` to store the maximum value of \( \text{values[i]} + i \) encountered so far.

#### Iterating Through the Array:

- For each \( j \) (starting from the second element):
  - Compute the score using the current \( \text{max\_i\_value} \) and \( \text{values[j]} - j \).
  - Update `max_score` if the current score is greater than the previous maximum.
  - Update `max_i_value` to account for \( \text{values[j]} + j \).

#### Efficiency:

- The solution runs in \( O(n) \) time, as it involves a single loop through the array.
- The space complexity is \( O(1) \), as no additional storage proportional to the input size is used.


![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']