Java O(n), easy to understand
This Solution is inspired by Buy and Sell Stock. \nIn that problem we are required to work out the maximum value of A[j]-A[i]forj>i, so we need to record the mi
This Solution is inspired by Buy and Sell Stock. \nIn that problem we are required to work out the maximum value of `A[j]-A[i]`for`j>i`, so we need to record the minimum value of `A[i]` and maximum value of `A[j]-A[i]`.  \nIn this problem, `A[i]+A[j]+i-j`can be converted to`(A[j]-j)+(A[i]+i)`, so instead of record the minimum value of `A[i]`, we can use `max` to track the maximum value of `A[i]+i` and maximum value of `A[j]-j+max`.\nI think there exsits a template for this kind of problem, we can seperated `i` and `j` first and record their values.\n```\nclass Solution {\n    public int maxScoreSightseeingPair(int[] A) {\n        int max = 0, res = 0;\n        for (int i = 0; i < A.length; i ++) {\n            res = Math.max(res, A[i]-i+max);\n            max = Math.max(max, A[i]+i);\n        }\n        return res;\n    }\n}\n```
[]