最佳观光组合

解题思路

主要要理解：最大化 A[i]+i+A[j]-j 的值其实就等价于求 [0,j-1] 中 A[i]+i 的最大值 mx，景点 j 的答案即为 mx+A[j]-j

代码

java

class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        int res = 0;
        int mx = A[0]+0;
        for(int j=1;j<A.length;j++){
            res = Math.max(res, mx+A[j]-j);
            mx = Math.max(mx, A[j]+j);
        }
        return res;
    }
}