Intuition

To solve the problem of finding the maximum score for a pair of sightseeing spots, we can break down the score equation as follows:

The score is given by:

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

This can be rearranged as:

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

the term (values[i] + i) depends only on i, and (values[j] - j) depends only on j. This allows us to use a greedy approach to compute the maximum score efficiently.

Approach

1. Iterate Over values:

2. Keep track of the maximum value of (values[i] + i) encountered so far.

3. Calculate Scores:

4. For each index i (starting from 1), compute the potential score using: prev_max_score + values[i] - i

5. Update prev_max_score: Update the maximum value of (values[i] + i) as you iterate through the array.

Complexity:

• Time complexity: O(N).
• Space complexity: O(1) for constant space used for variables.

Code

Go

func maxScoreSightseeingPair(values []int) int {
    n := len(values)
    ans := 0
    prevMaxValue := values[0]
    for i := 1; i < n; i++ {
        ans = max(ans, prevMaxValue + values[i] - i)
        prevMaxValue = max(prevMaxValue, values[i] + i)
    }
    return ans
}

Rust

impl Solution {
    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut n = values.len();
        let mut prev_max_score = values[0];
        for i in 1..n {
            ans = ans.max(prev_max_score + values[i] - i as i32);
            prev_max_score = prev_max_score.max(values[i] + i as i32);
        }
        ans
    }
}