Best Sightseeing Pair | Explained | BruteForce and DP one pass
1. Brute Force Soulution\n\nFind all the pairs and find the best score in it.\n\n\nint maxScoreSightseeingPair(vector<int>& values) {\n        int ans = 0;\n   
**1. Brute Force Soulution**\n\nFind all the pairs and find the best score in it.\n\n```\nint maxScoreSightseeingPair(vector<int>& values) {\n        int ans = 0;\n        \n        for(int i = 0; i < values.size(); i++) {\n            for(int j = i+1; j < values.size(); j++) {\n                int score = values[i] + values[j] + i - j;\n                \n                ans = max(ans, score);\n            }\n        }\n        \n        return ans;\n    }\n```\n\n**2. DP memorization**\n\nNote that the `score` value consists of two parts.\nWe are going to find the index of best left pair as we iterate through the values, and cache them in `bestScore`.\n\n![image](https://assets.leetcode.com/users/images/c30bfd34-6f84-4242-b961-d5ed6c4d9f12_1654883343.253127.png)\n\nAt each time we move j,\n1) Can index j-1 can be the new i? Then update `bestScore`.\n2) Update `ans` value with `max(ans, score(i,j))`.\n\n```\nint maxScoreSightseeingPair(vector<int>& values) {\n        int ans = 0;\n        int bestscore = 0;\n        \n        for(int i = 1; i < values.size(); i++) {\n            bestscore = max(bestscore, values[i-1]+i-1);\n            ans = max(ans, bestscore+values[i]-i);\n        }\n        \n        return ans;\n    }\n```
['C', 'C++']