1014题目

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-sightseeing-pair
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题过程

看到题目，第一印象就是两层循环暴力计算，如下

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function(A) {
    let max=0;
    for(var i=0;i<A.length;i++){
        for(var j=i+1;j<A.length;j++){
            if(A[i]+A[j]+i-j>max){
                max=A[i]+A[j]+i-j;
            }
        }
    }
    return max;
};

function print(str){
    console.log(str);
}

(function (){
    var input=[8,1,5,2,6];
    var output=maxScoreSightseeingPair(input);
    print(input);
    print(output);
}());

但是显然时间复杂度为n2，显然这不是出题者的本意；提交结果也说明了效率很低。

3.png
看了讨论后，发现还能这么做，既然能固定A[j]-j，那么也能固定A[i]+i，于是整理如下代码。

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function(A) {
    let max=0;
    for(var i=0;i<A.length;i++){
        for(var j=i+1;j<A.length;j++){
            if(A[i]+A[j]+i-j>max){
                max=A[i]+A[j]+i-j;
            }
        }
    }
    return max;
};

var maxScoreSightseeingPair2 = function(A) {
    let max_Ai_plus_i=A[0];
    let max=0;
    for(var j=1;j<A.length;j++){
        if(max<max_Ai_plus_i+A[j]-j){
            max=max_Ai_plus_i+A[j]-j
        }
        if(max_Ai_plus_i<A[j]+j){
            max_Ai_plus_i=A[j]+j;
        }
    }
    return max;
};

var maxScoreSightseeingPair3 = function(A) {
    let j_index=A.length-1
    let max_Aj_minus_j=A[j_index]-j_index;
    let max=0;
    for(var i=A.length-2;i>=0;i--){
        if(max<max_Aj_minus_j+A[i]+i){
            max=max_Aj_minus_j+A[i]+i
        }
        if(max_Aj_minus_j<A[i]-i){
            max_Aj_minus_j=A[i]-i;
        }
    }
    return max;
};

function print(str){
    console.log(str);
}

(function (){
    var input=[8,1,5,2,6];
    var output=maxScoreSightseeingPair(input);
    var output2=maxScoreSightseeingPair2(input);
    var output3=maxScoreSightseeingPair3(input);
    print(input);
    print(output);
    print(output2);
    print(output3);
}());

结果如预料的一样，效率提高了

4.png