Best Sightseeing Pair

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;
    }
};

The solution provided outlines an efficient approach to solve the 'Best Sightseeing Pair' problem using C++. The main idea is to maximize the score of the sightseeing pairs, given by values[i] + values[j] + i - j, by iterating through the array of values and keeping track of the best potential scores for sightseeing, both leftwards and rightwards.

• The code initiates by storing the length of the input vector, arr, and setting optimumLeftScore to the first element value since it serves as a base for comparing all other possible pairs.
• It also initializes highestScore to zero, which is intended to store the maximum score found during the iterations.
• The loop starts from the second element of the list, indexing through every element to compute two main evaluations:
  • evalRightScore calculates the diminishing value contribution of an element based on its position in the array.
  • At every iteration, the current highest possible score is updated by comparing highestScore with the sum of optimumLeftScore (which accounts for the maximum value sightseen up to the previous point adjusted for its distance) and evalRightScore.
  • evalLeftScore updates the possible maximum value of sightseeing from the current position, inclusive of the forward positional advantage.
• After iterating through the array, highestScore holds the maximum sightseeing score achievable and is returned as the output.

This C++ implementation provides an O(n) solution to the problem by compromising space complexity for time efficiency, ensuring each element is visited no more than once for direct calculations without needing nested iterations.

class Solution {

    public int maximumScoreSightseeingPair(int[] scores) {
        int length = scores.length;

        // Set initial max left score to first element.
        int maxLeft = scores[0];

        int highestScore = 0;

        for (int j = 1; j < length; j++) {
            int rightScore = scores[j] - j;
            // Calculate max combination of scores with the max left seen so far.
            highestScore = Math.max(highestScore, maxLeft + rightScore);

            int leftScore = scores[j] + j;
            // Refresh the max left score as needed.
            maxLeft = Math.max(maxLeft, leftScore);
        }

        return highestScore;
    }
}

You'll find a Java solution here for calculating the maximum score from the "Best Sightseeing Pair" problem. It optimizes the computation by keeping track of the highest score during one iteration over the array.

• First, initialize two integers: one to store the maximum left value (maxLeft) which starts from the first score combined with its index, and another (highestScore) to keep the current highest score which initially is zero.
• Iterate through the scores array starting from the second score because the first score is already used to initialize maxLeft.
• For each element in the scores array:
  1. Subtract the current index from the score to adjust for decreasing sightseeing impact with distance, referred to as rightScore.
  2. Update highestScore which is the maximum of its current value or the sum of maxLeft and rightScore.
  3. Compute a new left score which adds the current score to the current index, then update maxLeft to be the maximum of its current value or this new score.
• Return the highestScore which now holds the maximum sightseeing pair score after scanning through the list.

This ensures that at every step, you have the optimal score viewed from any previous point combined with the current point considering the distance penalty, all in O(n) complexity.

class Solution:
    def maxScoreSightseeingPair(self, vals):
        length = len(vals)

        max_left = vals[0]
        highest_score = 0

        for j in range(1, length):
            right_score = vals[j] - j
            highest_score = max(highest_score, max_left + right_score)

            left_score = vals[j] + j
            max_left = max(max_left, left_score)

        return highest_score

In this solution, you tackle the problem of identifying the best sightseeing pair, where the sum of values of two locations minus the distance between them needs to be maximized. This Python3 solution uses an efficient approach based on dynamic programming principles instead of a brute force O(n^2) solution. Here’s how the solution operates:

1. Initialize two variables, max_left, which keeps track of the maximum value encountered so far adjusted by the index, and highest_score which captures the highest score found.

2. Loop through the input list vals starting from the second element (since index pairs must be different, i.e., i ≠ j).

3. For each position j, calculate right_score which is the value at vals[j] minus the index j. This computes the score part attributed to the current position j assuming it's the end of the sightseeing pair.

4. Update highest_score by taking the maximum of itself and the sum of max_left and right_score. max_left represents the best possible start of the sightseeing pair seen so far.

5. Compute left_score for the current index j, which could potentially become the best start for any subsequent pairs.

6. Update max_left to ensure it holds the maximum sightseeing value including index adjustments for any possible start indices.

7. After the loop terminates, highest_score contains the maximum possible score for any sightseeing pair in the array.

By using max_left to remember the best possible values and updating the highest score as you process each element, this algorithm efficiently finds the optimal solution with a time complexity of O(n), which is much faster for larger lists compared to a direct nested loop approach.