TC : O(n) | SC : O(1) | C++ | Java | Python | Easy Solution
Intuition\nEver been on a sightseeing trip where you\'re trying to maximize your Instagram likes? Well, this problem is kinda like that, but with less selfie st
# Intuition\nEver been on a sightseeing trip where you\'re trying to maximize your Instagram likes? Well, this problem is kinda like that, but with less selfie sticks and more math. To find the dynamic duo of spots that\'ll make our vacation album pop. We keep track of the best spot we\'ve seen so far (let\'s call it our "selfie hotspot") and compare it with each new spot we encounter. It\'s like playing "Hot or Not" with tourist attractions!\n\n# Approach\nOur approach is to use a greedy strategy to keep track of the maximum score. We\'ll maintain two variables: `maxi`, to keep track of the index of the spot with the maximum score so far, and `ans` to store the maximum score. \nAs we iterate through the list, we\'ll update maxi whenever we find a spot with a higher score, and we\'ll update ans whenever we find a pair with a higher score. The trick is to calculate the score for each pair in O(1) time by using the fact that the score is values[i] + values[j] + i - j, where i and j are the indices of the two spots.\n\n# Complexity\n- Time complexity:\nThe time complexity is \uD835\uDC42(\uD835\uDC5B), where n is the number of sightseeing spots. We\'re taking a leisurely stroll through the array, no rush, just one pass!\n\n- Space complexity:\nThe space complexity is \uD835\uDC42(1) since we\'re traveling light - just a couple of variables in our backpack. Marie Kondo would be proud!\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int maxi = 0;\n        int ans = 0;\n\n        for(int i=1; i<values.size(); i++) {\n            ans = max(ans, values[i] + values[maxi] + (maxi - i));\n\n            if(values[i] + i >= values[maxi] + maxi) {\n                maxi = i;\n            }\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public int maxScoreSightseeingPair(int[] values) {\n        int maxi = 0;\n        int ans = 0;\n\n        for(int i=1; i<values.length; i++) {\n            ans = Math.max(ans, values[i] + values[maxi] + (maxi - i));\n\n            if(values[i] + i >= values[maxi] + maxi) {\n                maxi = i;\n            }\n        }\n        return ans;\n    }\n}\n```\n```python []\nclass Solution:\n    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n        maxi = 0\n        ans = 0\n\n        for i in range(1, len(values)):\n            ans = max(ans, values[i] + values[maxi] + (maxi - i))\n\n            if values[i] + i >= values[maxi] + maxi:\n                maxi = i\n\n        return ans\n```\n\nPlease upvote if you like the solution!\n
['Array', 'Greedy', 'C++', 'Java', 'Python3']