✅ 🔥 BEATS 100% PROOF🔥|| 💡 CONCISE CODE ✅ || 🌟 JAVA || 🧑‍💻 BEGINNER FREINDLY
📝 Proof💡 IntuitionThe formula for the score is: score = values[i] + values[j] + i - j.This can be rewritten as: score = (values[i] + i) + (values[j] - j).Here:
```
```
# 📝 Proof
---
![image.png](https://assets.leetcode.com/users/images/f8229824-be31-42b1-9d33-7b6240a5b841_1735258200.0522504.png)

---
```
```
# 💡 Intuition
---
<!-- Describe your first thoughts on how to solve this problem. -->
### The formula for the score is: `score = values[i] + values[j] + i - j`.
### This can be rewritten as: `score = (values[i] + i) + (values[j] - j)`.
### Here:
- `values[i] + i` represents the "potential" of the first sightseeing spot `i`.
- `values[j] - j` represents the "reduced" value of the second sightseeing spot `j` due to the distance penalty.
```
```
---
```
```
# 🧠 Approach
---
<!-- Describe your approach to solving the problem. -->
### 1. Keep track of the maximum value of `values[i] + i` (denoted as `m`) as you iterate through the array.
### 2. For each index `j`:
- Calculate the score using the formula: `m + values[j] - j`.
- Update the maximum score (`ans`) based on the current score.
### 3. Update m to be the maximum of its current value and `values[j] + j`, which accounts for the new index `j`.
### 4. Repeat this for all indices and return the maximum score.
```
```
---
```
```
# 🌟 Complexity
---
### 1. Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- $$O(n)$$, as we only traverse the array once.
---
### 2. Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
- $$O(1)$$, as no extra space is used.
```
```
---
```
```
# 🏷️ Concept of Tags Used
---
### 1. Greedy Algorithm:
- The solution uses a greedy approach by maintaining the best possible value (`m`) of `values[i] + i` up to the current index. At each step, it calculates the score for index `j` and updates `m` for future iterations.
### 2. Array:
- The input is an array of integers, and the operations are performed using array indexing to calculate the required scores efficiently.
### 3. Dynamic Programming Concept:
- Although this problem does not use a formal DP table, it employs a similar concept by maintaining the maximum value of `values[i] + i` dynamically as the iteration progresses.
### 4. Two Pointers (Implicit):
- The solution indirectly mimics a two-pointer-like behavior by keeping track of the best `i` for each `j` without explicitly using two pointers.
```
```
---
```
```
# 📒 Code
---
```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = Integer.MIN_VALUE;
        int m = values[0];

        for (int i = 1; i < values.length; i++) {
            if (values[i] - i + m > ans) 
                ans = values[i] - i + m;
            
            if (values[i] + i > m) 
                m = values[i] + i;
        }

        return ans;
    }
}
```
```
```
---
![upvote.png](https://assets.leetcode.com/users/images/e8d6f929-2f56-4114-985c-8f98a8b737cc_1735258244.581835.png)

---
```
```
['Array', 'Two Pointers', 'Greedy', 'Java']