Simple Explanation : DP solution O(n) time, O(1) space
Very Simple Approach : \nFor each index, store the maximum score ending at current index.\nFor example :\nA = [8,1,5,2,6]\nlet B  represent the maximum score su
# Very Simple Approach : \nFor each index, store the maximum score ending at current index.\nFor example :\nA = [8,1,5,2,6]\nlet B  represent the maximum score such that current index is end point (j);\nBase Cases : B[0] and B[1]\nB[0] = 0 (B[0] is not under consideration as A.size >= 2 and i>j as per question)\nB[1] = 8 + 1 - 1 = 8\nRecursive Formula : for j >= 2\nB[i] = max(B[i-1]-A[i-1] + A[i] -1, A[i-1]+A[i]-1)\nour ans is max element of B;\nB[2] = 11\nB[3] = max(11-5+2-1, 5+2-1) = 7\nB[4] = max(7-2+6-1, 2+6-1) = 10\n\nSo our ans is : max element of B = 11\n\nImplementation 1:\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& val) {\n        int n = val.size();\n        vector<int> vec(n,0);\n        vec[1] = val[0]+val[1]-1;\n        int ans = vec[1];\n        for(int i=2;i<n;i++){\n            vec[i] = max(vec[i-1]-val[i-1]+val[i]-1,val[i-1]+val[i]-1);\n            ans = max(vec[i],ans);\n        }\n        return ans;\n    }\n};\n// Time Complexity : O(n)\n// Space Complexity : O(n)\n```\n\nSpace can be optimized to O(1) because only one previous val of array is being used\n\nImplementation 2:\n\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& val) {\n        int n = val.size();\n        int cur;\n        cur = val[0]+val[1]-1;\n        int ans = cur;\n        for(int i=2;i<n;i++){\n            int cur1;\n            if(cur-val[i-1]+val[i]-1 > val[i-1]+val[i]-1){\n                cur1 = cur-val[i-1]+val[i]-1;\n            }\n            else{\n                cur1 = val[i-1]+val[i]-1;\n            }\n            ans = max(ans,cur1);\n            cur = cur1;\n        }\n        return ans;\n    }\n\t// Time Complexity : O(n)\n    // Space Complexity : O(1)\n};\n```\n**Important :** Interview follow-up question can be : Return indices i and j for optimal answer.\n\nWe can also recored the value of indices (i and j) corresponding to the optimal answer.\nTry doing this, Let me know in comments if you need solution of this variant also. \n
['Dynamic Programming']