JAVA O(N) solution with explanation
Approach\n1) The idea is to see the expression given that is value[i] + values[j] + i - j.\n2) Expression can also be seen as (values[i] + i) + (values[j] - j).
Approach\n1) The idea is to see the expression given that is value[i] + values[j] + i - j.\n2) Expression can also be seen as (values[i] + i) + (values[j] - j).\n3) Now just keep the track of the maximum of (values[i] + i) upto current index and update the max answer.\n4) Below is the implementation of the same\n```\nclass Solution {\n    public int maxScoreSightseeingPair(int[] values) {\n        int max = values[0];\n        int i = 1;\n        int ans = max;\n        while (i < values.length) {\n            ans = Math.max(ans,max + values[i] - i);\n            max = Math.max(max,values[i] + i);\n            i++;\n        }\n        return ans;\n    }\n}\n```
[]