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