最佳观光组合

0x1 题目详情

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。

一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。

返回一对观光景点能取得的最高分。

输入：[8,1,5,2,6] 输出：11 解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

0x2 解题思路

看到这道题我的第一思路是先暴力递归，然后转成动态规划，但是我暴力了半天，不得已看了答案，发现竟然如此简单，我真想给自己一拳。

题目要求$A[i]+A[j]+i-j$的最大值，对其稍作变换，就转换为$A[i]-i+A[j]-j$,那么我们在遍历数组时，更新$A[i]-i$，然后每一轮都求一个最大值，最后结束时就是结果。

虽然我可以看到通过最佳买卖股票的时机的方法求，但是我研究了半天也没搞出来，希望有高人能指点我一哈。

0x3 代码实现

只需遍历一遍数组就可,时间复杂度为$O(N)$

class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        if(A== null || A.length==0){
            return 0;
        }
        int result=Integer.MIN_VALUE;
        int pre=A[0];
        for(int i=1;i<A.length;i++){
            //每一轮都更新最大值
            result=Math.max(result,pre+A[i]-i);
            //每一轮都更新最大的A[i]-i
            pre=Math.max(pre,A[i]+i);
        }
        return result;
    }
}

0x4 课后总结

罪过啊罪过，这么简单的题都没做出来，当然暴力的方法就说了，嘿嘿，不过这题跟动态规划有啥关系，咋啥都扯上动态规划了。