Simple DP Solution | O(N) | Very easy to understand
[8,1,5,2,6]. Let\'s take this example for better understanding. Assume this is 1-metered lenses game. Each number in the input vector represents number of lense
[8,1,5,2,6]. Let\'s take this example for better understanding. Assume this is *1-metered lenses* game. Each number in the input vector represents number of lenses you get on that location (each lense can cover 1-meter distance), so 8 in [8,1,5,2,6] says, being at that position, you can cover 8-meter since you\'re having 8 1-metered lenses. You\'ve to find out the maximum distance you can cover with the help those lenses.\n\nThere are 2 rules to this game,\n* You can use maximum 2 positions\' lenses at a time. One will be in your hand and other you\'ll pick as you go to that position.\n* You lose 1 lense you currently have in your hand each time you move forward.\n\nStrategy to deal with this game is,\n1. Take all the lenses of first location. i.e. 8 in our case.\n2. Go forward, you\'ll have 7 lenses with you. Note the maximum distance you can cover with the help of lenses you kept with you and lenses you\'ve available at this position which is 7+1.\n3. Make decision of which of the lenses you want to move forward with? One you bring from previous positions or one you got from this position. (i.e. 7 lenses or 1 lense).\n4. Repeat steps 2 and 3 for all the positions. \n\nYou\'ll end up getting maximum distance you can cover with all the rules of the game.\n\n`currMx`: Lenses you\'ll be keeping in your hand each time going forward in the iteration.\n`mxScore`: Maximum distance you can cover.\n\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int mxScore = 0;\n        int currMx = values[0];\n        \n        for(int i=1; i<values.size(); i++){\n            currMx--;\n            mxScore = max(values[i]+currMx, mxScore);\n            currMx = max(values[i], currMx);\n        }\n        \n        return mxScore;\n        \n    }\n};\n```
['Dynamic Programming', 'C', 'C++']