simple java solution with explaination from brute force to dp, single pass
Approach 1->\nbrute force solution of trying every possible pair and keep on updating max will take o(n^2) and will result in TLE.\n\npublic int maxScoreSightse
**Approach 1->**\nbrute force solution of trying every possible pair and keep on updating max will take o(n^2) and will result in TLE.\n```\npublic int maxScoreSightseeingPair(int[] values) {\n       int max=0;\n        for(int i=0;i<values.length;i++) {\n            for(int j=i+1;j<values.length;j++) {\n                int spot = values[i] + values[j] + i - j;\n                max=Math.max(spot,max);\n            }\n        }\n        return max;\n    }\n```\n**Approach 2 ->**\n\nIf you look at the code it is quite short. but to understand the solution it will take time.\nmaximize = (a[i]+a[j]+i-j) and i<j\nit means we cannot go back. We can write above equation as \nmax = max(a[i]+i)+max(a[j]-j)\n1. Now keep track of maximum a[i]+i till ith iteration.\n2. use that above ith max value and add it to a[j]-j to keep track of maximum answer.\n3. Now, since we are dealing with single loop we need to make sure that when we want to compute a[j]-j+maxi, maxi should point to the maximum till j-1 index.\nso, using above idea below solution will work\ninitialize maxI with 0. and when we want to compute ans, just use values[i]-i+maxI. once calculated compute maxI again for next computation. in this way maxI will always point to one less index and store the result of max(values[i]+i)\n```\npublic int maxScoreSightseeingPair(int[] values) {\n       //hold max(A[i]+i)\n        int maxI=0;\n\t\t//hold the final answer\n        int ans=0;\n        for(int i=0;i<values.length;i++) {\n            ans=Math.max(ans,maxI+values[i]-i);\n            maxI=Math.max(maxI,values[i]+i);\n        }\n        return ans;\n    }\n```
['Dynamic Programming', 'Java']