Best Sightseeing Pair

Leetcode Problem:

• Best Sightseeing Pair

Summary

• Given an array of sightseeing spot values, find the maximum score of a pair of sightseeing spots.

Approach

• This problem can be solved using dynamic programming
• We maintain two arrays: maxLeftScore and maxRightScore
• maxLeftScore[i] represents the maximum score of a sightseeing spot at index i from the left, and maxRightScore[i] represents the maximum score of a sightseeing spot at index i from the right
• We update these arrays iteratively, and the maximum score is the maximum of the sum of maxLeftScore[i-1] and maxRightScore[i], or maxLeftScore[i-1] plus the current right score.

Complexity

• O(n)

Explanation

• The time complexity is O(n) because we are iterating through the array once
• The space complexity is O(n) because we are storing the maximum left and right scores for each index.

Solution Code:

class Solution {
public:
    int maxScoreSightseeingPair(vector& values) {
        int n = values.size();
        // Initialize an array to store the maximum left scores up to each
        // index.
        vector maxLeftScore(n);
        // The left score at the first index is just the value of the first
        // element.
        maxLeftScore[0] = values[0];

        int maxScore = 0;

        for (int i = 1; i < n; i++) {
            int currentRightScore = values[i] - i;
            // Update the maximum score by combining the best left score so far
            // with the current right score.
            maxScore = max(maxScore, maxLeftScore[i - 1] + currentRightScore);

            int currentLeftScore = values[i] + i;
            // Update the maximum left score up to the current index.
            maxLeftScore[i] = max(maxLeftScore[i - 1], currentLeftScore);
        }

        return maxScore;
    }
};