Solution for LeetCode#1014
IntuitionThe problem asks to find the maximum score of a sightseeing pair, where the score is calculated as values[i] + values[j] + i - j (i < j). The key insig
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem asks to find the maximum score of a sightseeing pair, where the score is calculated as values[i] + values[j] + i - j (i < j). The key insight is to realize that we can split this formula into (values[i] + i) + (values[j] - j) and optimize these two parts separately.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Initialize iSite with the score of the first site (values + 0).
2. Iterate through the array starting from the second element:
	- Calculate the potential score if the current site is paired with the best previous site.
	- Update maxScore if this potential score is higher.
	- Update iSite to be the maximum of the current iSite and the score of the current site (values[i] + i).

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code Option-01
![image.png](https://assets.leetcode.com/users/images/267d1635-3f5f-4281-bd0c-3e5123a64f51_1735269371.2912648.png)

```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int n=values.length;

        int iSite=values[0]+0;        
        int maxScore=0;
        for(int i=1; i<n; i++){
            maxScore=Math.max(maxScore, iSite+values[i]-i); // values[i]+i + values[j]-j  where i<j
            iSite=Math.max(iSite, values[i]+i);
        }


        return maxScore;
    }
}
```

# Code Option-02
![image.png](https://assets.leetcode.com/users/images/ef0474b2-4cbd-41c9-8da9-de527bb43540_1735269427.460372.png)

```java []
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int n=values.length;

        int iSite=values[0]+0;        
        int maxScore=0;
        for(int i=1; i<n; i++){ 
            if(maxScore<iSite+values[i]-i)
                maxScore=iSite+values[i]-i; // values[i]+i + values[j]-j  where i<j
            
            if(iSite < values[i]+i)
                iSite=values[i]+i;  
        }


        return maxScore;
    }
}
```
['Java']