🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
IntuitionThe problem involves finding the maximum score between two sightseeing spots. For two indices i and j (i < j), the score is defined as:
values[i] + val
![image.png](https://assets.leetcode.com/users/images/0506b28c-a51b-4b8b-b3f0-1e698521a31d_1735284431.1938963.png)

---
![1000043181.png](https://assets.leetcode.com/users/images/c363abe8-90a7-44e5-9f81-20df2dcf6f62_1735286708.0527341.png)

---

### Intuition
The problem involves finding the maximum score between two sightseeing spots. For two indices `i` and `j` (`i < j`), the score is defined as:  
**`values[i] + values[j] + i - j`**.  

To maximize the score, we need to consider the combination of:
1. `values[i] + i` — this represents the contribution of the left sightseeing spot.
2. `values[j] - j` — this represents the contribution of the right sightseeing spot minus its positional penalty.  

Thus, at each index `j`, the goal is to:
- Find the best `values[i] + i` (for all `i < j`) to maximize the score when combined with `values[j] - j`.

### Approach
1. Initialize a variable `bestLeft` to store the maximum value of `values[i] + i` seen so far as we iterate through the array.
2. Iterate through the array starting from the second element (`j = 1`):
   - Calculate the score for the current pair using the formula:  
     **`maxScore = max(maxScore, bestLeft + values[j] - j)`**.
   - Update `bestLeft` for future pairs using the formula:  
     **`bestLeft = max(bestLeft, values[j] + j)`**.
3. Return the maximum score after iterating through the array.

### Complexity
- **Time Complexity**: $$O(n)$$, as we traverse the array once.
- **Space Complexity**: $$O(1)$$, as no additional space is used beyond a few variables.

---

### Code
```dart []
import 'dart:math';

class Solution {
  int maxScoreSightseeingPair(List<int> values) {
    int maxScore = 0; // To store the maximum score
    int bestLeft = values[0]; // The best "values[i] + i" seen so far

    for (int j = 1; j < values.length; j++) {
      // Compute the score for the current pair
      maxScore = max(maxScore, bestLeft + values[j] - j);

      // Update the best "values[i] + i" for future pairs
      bestLeft = max(bestLeft, values[j] + j);
    }

    return maxScore;
  }
}
```


```python []
class Solution:
    def maxScoreSightseeingPair(self, values):
        max_score = 0
        best_left = values[0]  # The best "values[i] + i" seen so far

        for j in range(1, len(values)):
            # Compute the score for the current pair
            max_score = max(max_score, best_left + values[j] - j)

            # Update the best "values[i] + i" for future pairs
            best_left = max(best_left, values[j] + j)

        return max_score
```


```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int bestLeft = values[0]; // The best "values[i] + i" seen so far

        for (int j = 1; j < values.length; j++) {
            // Compute the score for the current pair
            maxScore = Math.max(maxScore, bestLeft + values[j] - j);

            // Update the best "values[i] + i" for future pairs
            bestLeft = Math.max(bestLeft, values[j] + j);
        }

        return maxScore;
    }
}
```


```cpp []
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int maxScore = 0;
        int bestLeft = values[0]; // The best "values[i] + i" seen so far

        for (int j = 1; j < values.size(); j++) {
            // Compute the score for the current pair
            maxScore = max(maxScore, bestLeft + values[j] - j);

            // Update the best "values[i] + i" for future pairs
            bestLeft = max(bestLeft, values[j] + j);
        }

        return maxScore;
    }
};
```


```go []
package main

import "math"

func maxScoreSightseeingPair(values []int) int {
    maxScore := 0
    bestLeft := values[0] // The best "values[i] + i" seen so far

    for j := 1; j < len(values); j++ {
        // Compute the score for the current pair
        maxScore = int(math.Max(float64(maxScore), float64(bestLeft+values[j]-j)))

        // Update the best "values[i] + i" for future pairs
        bestLeft = int(math.Max(float64(bestLeft), float64(values[j]+j)))
    }

    return maxScore
}
```


```javascript []
var maxScoreSightseeingPair = function(values) {
    let maxScore = 0;
    let bestLeft = values[0]; // The best "values[i] + i" seen so far

    for (let j = 1; j < values.length; j++) {
        // Compute the score for the current pair
        maxScore = Math.max(maxScore, bestLeft + values[j] - j);

        // Update the best "values[i] + i" for future pairs
        bestLeft = Math.max(bestLeft, values[j] + j);
    }

    return maxScore;
};
``` 


---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}


['C', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']