C++ | Very Easy O(n) Code with Explanation
Explanation : \n\nSuppose we have [8,1,9,2,5]\nSuppose the current index is j & second index we will take be x (x>j).\nThe value = (value[j] + j) + (values[x] -
Explanation : \n\nSuppose we have [8,1,9,2,5]\nSuppose the current index is j & second index we will take be x (x>j).\nThe value = (value[j] + j) + (values[x] - x) ;\n\nSo whatever be the x, if we, moving from 0 -> n, keep track of the maximum ( index + val[index] ), then we can optimally find the best pairs. \n\nPlease Upvote :)\n\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int j=0;\n        int res=0;\n        // store max of values[j] + j as you move forward. \n        for(int i=1;i<values.size();i++)\n        {\n            res=max(res,values[i]+values[j]+j-i);\n            if(values[i]+i > values[j]+j)\n                j=i;\n        }\n        return res;\n    }\n};\n```
['C', 'C++']