1014題目

給定正整數(shù)數(shù)組 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有喇喉。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)祖今，非商業(yè)轉(zhuǎn)載請注明出處。

解題過程

看到題目，第一印象就是兩層循環(huán)暴力計算千诬，如下

/**
 * @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);
}());

但是顯然時間復(fù)雜度為n2耍目，顯然這不是出題者的本意；提交結(jié)果也說明了效率很低徐绑。

3.png

/**
 * @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);
}());

結(jié)果如預(yù)料的一樣盘榨，效率提高了

4.png