🌟 Dynamic Programming,🤝 the Greedy Way: 🧠 Optimized Sightseeing ||💥Beginner-Friendly✨
Intuition 🌟We want to maximize the score for a sightseeing pair:By rewriting it ✍️:Key Insight 💡:To maximize the score, we keep track of the maximum value ofas
# Intuition 🌟
We want to maximize the score for a sightseeing pair:

    score(i,j)=values[i]+values[j]+i−j

By rewriting it ✍️:
 
    score(i,j)=(values[i]+i)+(values[j]−j)

Key Insight 💡:

    The term (values[i]+i) depends only on i.

    The term (values[j]−j) depends only on j.
To maximize the score, we keep track of the maximum value of  

    (values[i]+i)
as maxValue while iterating through the array. At each j, we calculate: 

-     score=maxValue+(values[j]−j)

and update maxValue for the next iterations.

---


# Approach 🛠️
1️⃣ Initialize:

    maxValue = values[0] + 0
(track the maximum of  

    (values[i]+i)) 🏆.

    ans = -\infty (start with the smallest possible score 🔥).
2️⃣ Iterate 🚀:

For every index  
Compute the score for the current sightseeing pair: 

    ans=max(ans,maxValue+values[j]−j)
Update maxValue for future pairs: 

    maxValue=max(maxValue,values[j]+j)
3️⃣ Return the maximum score (ans) 🎯.

---

# Complexity ⏱️
- Time Complexity:  

    
        O(n) 🏃‍♂️

    A single loop to calculate the score.
- Space Complexity:  

        O(1) 💾

    Only a few variables are used.


---

# Code
```cpp []
class Solution { 
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = INT_MIN;
        int n = values.size();
        int maxValue = values[0] + 0;

        for(int j = 1; j < n; j++) {  
            ans = max(ans, maxValue + values[j]-j);
            maxValue = max(maxValue, values[j] + j);
        }
        return ans;
    }
};
```

```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxScore = Integer.MIN_VALUE;
        int maxValue = values[0];
        
        for (int j = 1; j < values.length; j++) {
            maxScore = Math.max(maxScore, maxValue + values[j] - j);
            maxValue = Math.max(maxValue, values[j] + j);
        }
        return maxScore;
    }
}

```
```python []
class Solution:
    def maxScoreSightseeingPair(self, values: list[int]) -> int:
        max_score = float('-inf')
        max_value = values[0]
        
        for j in range(1, len(values)):
            max_score = max(max_score, max_value + values[j] - j)
            max_value = max(max_value, values[j] + j)
        
        return max_score

```
```javascript []
var maxScoreSightseeingPair = function(values) {
    let maxScore = -Infinity;
    let maxValue = values[0];
    
    for (let j = 1; j < values.length; j++) {
        maxScore = Math.max(maxScore, maxValue + values[j] - j);
        maxValue = Math.max(maxValue, values[j] + j);
    }
    return maxScore;
};

```
```ruby []
def max_score_sightseeing_pair(values)
    max_score = -Float::INFINITY
    max_value = values[0]
    
    (1...values.length).each do |j|
        max_score = [max_score, max_value + values[j] - j].max
        max_value = [max_value, values[j] + j].max
    end
    
    max_score
end

```
```rust []
impl Solution {
    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
        let mut max_score = i32::MIN;
        let mut max_value = values[0];
        
        for j in 1..values.len() {
            max_score = max_score.max(max_value + values[j] - j as i32);
            max_value = max_value.max(values[j] + j as i32);
        }
        
        max_score
    }
}

```
```c# []
public class Solution {
    public int MaxScoreSightseeingPair(int[] values) {
        int maxScore = int.MinValue;
        int maxValue = values[0];
        
        for (int j = 1; j < values.Length; j++) {
            maxScore = Math.Max(maxScore, maxValue + values[j] - j);
            maxValue = Math.Max(maxValue, values[j] + j);
        }
        return maxScore;
    }
}

```
```go []
func maxScoreSightseeingPair(values []int) int {
    maxScore := -int(^uint(0) >> 1) // Smallest int
    maxValue := values[0]
    
    for j := 1; j < len(values); j++ {
        maxScore = max(maxScore, maxValue + values[j] - j)
        maxValue = max(maxValue, values[j] + j)
    }
    return maxScore
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

```
```typescript []
function maxScoreSightseeingPair(values: number[]): number {
    let maxScore = Number.MIN_SAFE_INTEGER;
    let maxValue = values[0];
    
    for (let j = 1; j < values.length; j++) {
        maxScore = Math.max(maxScore, maxValue + values[j] - j);
        maxValue = Math.max(maxValue, values[j] + j);
    }
    return maxScore;
}

```
```swift []
class Solution {
    func maxScoreSightseeingPair(_ values: [Int]) -> Int {
        var maxScore = Int.min
        var maxValue = values[0]
        
        for j in 1..<values.count {
            maxScore = max(maxScore, maxValue + values[j] - j)
            maxValue = max(maxValue, values[j] + j)
        }
        return maxScore
    }
}

```
```dart []
int maxScoreSightseeingPair(List<int> values) {
    int maxScore = -double.maxFinite.toInt();
    int maxValue = values[0];
    
    for (int j = 1; j < values.length; j++) {
        maxScore = max(maxScore, maxValue + values[j] - j);
        maxValue = max(maxValue, values[j] + j);
    }
    return maxScore;
}

int max(int a, int b) => (a > b) ? a : b;

``` 
['Dynamic Programming', 'Greedy', 'Swift', 'Python', 'C++', 'Java', 'Ruby', 'JavaScript', 'C#', 'Dart']