πŸ“ Problem Details

πŸ’­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;
    }
};