# LeetCode 1014: Best Sightseeing Pair

## Problem Restatement

We are given an integer array `values` of length `n`.

The score of a pair `(i, j)` where `i < j` is:

```python
values[i] + values[j] + i - j
```

We need to return the maximum score over all valid pairs.

The official constraints state that `2 <= values.length <= 5 * 10^4` and `1 <= values[i] <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `values` |
| Output | Maximum score of any pair |
| Score formula | `values[i] + values[j] + i - j` |

Function shape:

```python
def maxScoreSightseeingPair(values: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
values = [8, 1, 5, 2, 6]
```

Best pair: `(0, 2)`: `8 + 5 + 0 - 2 = 11`.

Answer:

```python
11
```

Example 2:

```python
values = [1, 2]
```

Only pair: `(0, 1)`: `1 + 2 + 0 - 1 = 2`.

Answer:

```python
2
```

## Key Insight

Rewrite the score as:

```python
(values[i] + i) + (values[j] - j)
```

For a fixed `j`, the right term `(values[j] - j)` is fixed.

We want to maximize the left term `(values[i] + i)` over all `i < j`.

So we can scan from left to right, maintaining the best `(values[i] + i)` seen so far.

## Algorithm

1. Initialize `best_left = values[0] + 0`.
2. Initialize `result = 0`.
3. For each `j` from `1` to `n - 1`:
   - Update `result = max(result, best_left + values[j] - j)`.
   - Update `best_left = max(best_left, values[j] + j)`.
4. Return `result`.

The update order matters: we update `result` before updating `best_left` to ensure `i < j`.

## Correctness

At each position `j`, `best_left` holds the maximum `(values[i] + i)` for all `i < j`.

The current score for the best `i` and the current `j` is `best_left + values[j] - j`.

We track the maximum such score across all `j`.

After computing the score, we update `best_left` to include position `j` as a potential left index for future pairs.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Single pass |
| Space | `O(1)` | Constant extra space |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def maxScoreSightseeingPair(self, values: list[int]) -> int:
        best_left = values[0] + 0
        result = 0

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

        return result
```

## Code Explanation

`best_left` tracks the maximum `values[i] + i` seen so far:

```python
best_left = values[0] + 0
```

For each `j`, compute the best pair score using this left:

```python
result = max(result, best_left + values[j] - j)
```

Then update `best_left` to include position `j` as a future left:

```python
best_left = max(best_left, values[j] + j)
```

The update to `result` must come before the update to `best_left` to preserve the `i < j` constraint.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxScoreSightseeingPair([8, 1, 5, 2, 6]) == 11
    assert s.maxScoreSightseeingPair([1, 2]) == 2
    assert s.maxScoreSightseeingPair([1, 3, 5]) == 7
    assert s.maxScoreSightseeingPair([10, 1, 1]) == 10

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[8,1,5,2,6]` | `11` | Best pair is `(0,2)` |
| `[1,2]` | `2` | Only pair |
| `[1,3,5]` | `7` | Pair `(1,2)`: `3+5+1-2=7` |
| `[10,1,1]` | `10` | Best pair `(0,1)`: `10+1+0-1=10` |