1014. Best Sightseeing Pair

📝 Problem Details

• Title: 1014. Best Sightseeing Pair
• Link: https://leetcode.com/problems/best-sightseeing-pair/
• Difficulty: Medium
• Tags/Categories: Greedy Dynamic-Programming

💭What Were My Initial Thoughts?

- a brute force approach (with a TC of O(n^2)) would be to have a nested loop that calculates the score between two sightseeing spots, and keeps track of the highest value

- we need something more efficient than O(n^2), probably linear
- this problem seems similar to the problem 'best time to buy and sell stock'
- a greedy approach could work

🤔What Did I Struggle With?

~ translating the idea of a greedy approach into an algorithm 

💡 Explanation of Solution

- Start with a variable `maxScore` to store the maximum pair value.
- Maintain a running variable `bestI` for the maximum values[i] + i seen so far.
- For each j, calculate values[j] − j + bestI and update `maxScore` if it’s better.
- Update `bestI` as max⁡(bestI, values[j] + j)

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int maxScore = 0;      // Store the maximum score
        int bestI = values[0];      // Initialize the best A[i] + i seen so far
 
        // Iterate through the array starting from the second element
        for (int j = 1; j < values.size(); ++j) {
            // Calculate the score for the current pair (bestI and A[j])
            maxScore = max(maxScore, bestI + values[j] - j);
 
            // Update the bestI for the next iteration
            bestI = max(bestI, values[j] + j);
        }
 
        return maxScore;
    }
};