Best Sightseeing Pair

Problem Statement

In this problem, you are provided with an integer array named values, where each element in the array represents the value of a sightseeing spot. Each pair of indices i and j in the array has a distance j - i between them. You need to calculate the score for every possible pair (i, j) such that i < j. The score for a pair of sightseeing spots is computed using the formula values[i] + values[j] + i - j, which involves adding the values of the two spots and then subtracting the distance between them. The goal is to determine the maximum score obtainable from any pair of sightseeing spots in the array.

Examples

Example 1

Input:

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

Output:

11

Explanation:

i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2

Input:

values = [1,2]

Output:

2

Constraints

• 2 <= values.length <= 5 * 104
• 1 <= values[i] <= 1000

Approach and Intuition

To solve this problem optimally, understanding the relationship and manipulation of the indices along with their values is essential:

1. Idea Breakdown: The formula values[i] + values[j] + i - j can be rearranged to (values[i] + i) + (values[j] - j). This means that for every position j, if we can know the maximum value of (values[i] + i) for all i which are less than j, we can efficiently compute the maximum score up to position j.

2. Implementation Strategy:

   • Initialize a variable max_score to keep track of the maximum score found so far, and set it to a very low value initially.
   • Use another variable, say max_i_plus_val, to maintain the maximum value of (values[i] + i) as you iterate through the list from left to right.
   • For each j starting from the second element in the list:
     • Calculate (values[j] - j) and add it to max_i_plus_val to get a current score.
     • Update max_score if this current score is higher than what has been found so far.
     • Update max_i_plus_val to be the maximum of itself and (values[j] + j).

3. Efficiency: By maintaining the maximum (values[i] + i) seen so far and considering we only move forward in the list, each element is processed once, making the algorithm run in linear time O(n), where n is the number of sightseeing spots.

4. Example Handling:

   • In the example [8,1,5,2,6], processing will follow through calculating potential scores for every j starting from index 1, updating the potential maximum using past values up to that point, leading to a result of 11.

This approach efficiently handles the score computation by reorganizing the formula to separate parts dependent on past indices from parts dependent on the current index, allowing dynamic updating as we progress through the values list.

Solutions

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& arr) {
        int len = arr.size();
    
        int optimumLeftScore = arr[0];
        int highestScore = 0;
    
        for (int i = 1; i < len; i++) {
            int evalRightScore = arr[i] - i;
            highestScore = max(highestScore, optimumLeftScore + evalRightScore);
    
            int evalLeftScore = arr[i] + i;
            optimumLeftScore = max(optimumLeftScore, evalLeftScore);
        }
    
        return highestScore;
    }
};