最佳观光组合

1014. 最佳观光组合

给定正整数数组 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

提示：

1. 2 <= A.length <= 50000
2. 1 <= A[i] <= 1000

我们很轻松就可以写出暴力解法（超时）,时间复杂度 O(n^2)。

class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        int maxScore = Integer.MIN_VALUE;
        int n = A.length;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                maxScore = Math.max(maxScore, A[i] + A[j] + i - j);
            }
        }
        return maxScore;
    }
}

时间复杂度 O(n^2)，空间复杂度O(1)。

将得分A[i] + A[j] + i - j 拆分成 A[i]+ i和A[j] - j两个部分，仔细分析题意可知，在 i < j 时，对于每一个 j 值我们需要求得数组 A[0…j - 1]中的 A[i] + i 最大值，注意 i < j 这个条件，我们可以先求出下标 j 之前的 A[i] + i 最大值，并维护这个最大值 mx ，在 j 遍历过程中只用 O(1) 的时间即可求得 A[i] + i 最大值，遍历整个数组 A 需要O(n)，总时间复杂度 O(n)。

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

时间复杂度 O(n)，空间复杂度O(1)。