【算法】算法測(cè)試題5：牛牛的數(shù)列：最長(zhǎng)連續(xù)子序列

MRZYD 發(fā)布于2019-08-23 11:37 / 1899人閱讀

摘要：題目描述鏈接來(lái)源牛客網(wǎng)牛牛現(xiàn)在有一個(gè)個(gè)數(shù)組成的數(shù)列牛牛現(xiàn)在想取一個(gè)連續(xù)的子序列并且這個(gè)子序列還必須得滿足最多只改變一個(gè)數(shù)就可以使得這個(gè)連續(xù)的子序列是一個(gè)嚴(yán)格上升的子序列牛牛想知道這個(gè)連續(xù)子序列最長(zhǎng)的長(zhǎng)度是多少。

題目描述

鏈接：https://www.nowcoder.com/ques...
來(lái)源：牛客網(wǎng)

牛牛現(xiàn)在有一個(gè)n個(gè)數(shù)組成的數(shù)列,牛牛現(xiàn)在想取一個(gè)連續(xù)的子序列,并且這個(gè)子序列還必須得滿足:最多只改變一個(gè)數(shù),就可以使得這個(gè)連續(xù)的子序列是一個(gè)嚴(yán)格上升的子序列,牛牛想知道這個(gè)連續(xù)子序列最長(zhǎng)的長(zhǎng)度是多少。

輸入描述

輸入包括兩行,第一行包括一個(gè)整數(shù)n(1 ≤ n ≤ 10^5),即數(shù)列的長(zhǎng)度;
第二行n個(gè)整數(shù)a_i, 表示數(shù)列中的每個(gè)數(shù)(1 ≤ a_i ≤ 10^9),以空格分割。

輸出描述

輸出一個(gè)整數(shù),表示最長(zhǎng)的長(zhǎng)度。

示例1

輸入
6 
7 2 3 1 5 6
輸出
5

解題思路

分析：這道題目看上去沒(méi)法下手，就當(dāng)學(xué)習(xí)一個(gè)思路吧，首先根據(jù)當(dāng)前數(shù)組順著求一遍以每個(gè)位置作為結(jié)尾的連續(xù)最長(zhǎng)遞增子序列的長(zhǎng)度值，再逆著求解以每個(gè)元素作為開頭的連續(xù)最長(zhǎng)遞增子序列的長(zhǎng)度值，然后根據(jù)這兩組值來(lái)找連接點(diǎn)。具體就拿體重的例子來(lái)說(shuō)，此時(shí)數(shù)組arr為
7 2 3 1 5 6，我們定義兩個(gè)數(shù)組left
和right，left數(shù)組表示正著求以每個(gè)元素作為結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度，而right數(shù)組表示逆著以每個(gè)元素作為開頭的連續(xù)最長(zhǎng)遞增子序列的長(zhǎng)度值，所以可以知道left[0]=1,表示以7結(jié)尾的目前最長(zhǎng)的連續(xù)遞增子序列的長(zhǎng)度值就是1，依次left[1]=1,left[2]=2,left[3]=1,left[4]=2,left[5]=3;
而right[5]=1,right[4]=2,right[3]=3,right[2]=1,right[1]=2,right[0]=1;好了，到此為止兩個(gè)輔助的數(shù)組已經(jīng)求出，接下來(lái)就要找連接點(diǎn)了，是這樣的，根據(jù)題目意思，我們要找一個(gè)子序列，而且之多改變一個(gè)數(shù)就可以形成嚴(yán)格的連續(xù)遞增子序列，所以我們先盯住數(shù)組中2這個(gè)數(shù)，我們發(fā)現(xiàn)以7結(jié)尾的最長(zhǎng)的連續(xù)遞增子序列的長(zhǎng)度為left[0],而以3開頭的連續(xù)遞增子序列長(zhǎng)度為right[2]，這樣，我們其實(shí)不用管7和3之間的數(shù)到底是多少，是2也好，不是2也好，只要2前面的數(shù)7能夠嚴(yán)格小于2后面的數(shù)3，說(shuō)明通過(guò)改變7和3之間這個(gè)數(shù)至合適的數(shù)值則，這兩部分就可以連成一個(gè)連續(xù)的嚴(yán)格遞增子序列，所有，我們遍歷所有這樣的點(diǎn)，記錄滿足條件的最大的長(zhǎng)度再加1即可。
https://blog.csdn.net/wwe4023...

JavaScript代碼 JavaScript代碼1（雛形）

let n = parseInt(readline());
let t1 = readline();
let t2 = new String(t1);
let line = t2.split(" ");
let arr =  new Array();
for(let i = 0; i < line.length; i++){
    arr[i] = parseInt(line[i]);
}
let left = new Array(n);
let right = new Array(n);
let ans = 0;
for(let i = 0; i < arr.length; i++){
    left[i] = computeLeft(i, arr);
}
for(let i = arr.length - 1; i >= 0; i--){
    right[i] = computeRight(i, arr);
}
for(let i = 1 ; i < arr.length-1; i++){
    if(arr[i-1] <  arr[i+1]){
        let sum = left[i-1] + right[i+1];
        if(sum > ans){
            ans = sum;
        }
    }
}

print(ans+1);

function computeLeft(pos, arr){
    let count = 1;
    for(let i = pos; i > 0; i--){
        if(arr[i] > arr[i-1]){
            count++;
        }else{
            return count;
        }
    }
    return count;
}

function computeRight(pos, arr){
    let count = 1;
    for(let i = pos; i < arr.length-1; i++){
        if(arr[i] < arr[i+1]){
            count++;
        }else{
            return count;
        }
    }
    return count;

}

JavaScript代碼2（優(yōu)化）

let n = parseInt(readline());
let t1 = readline();
let t2 = new String(t1);
let line = t2.split(" ");
let arr =  new Array();
for(let i = 0; i < line.length; i++){
    arr[i] = parseInt(line[i]);
}
let left = new Array(n);//以arr[i]結(jié)尾的連續(xù)序列長(zhǎng)度
let right = new Array(n);//以arr[i]開頭的連續(xù)序列長(zhǎng)度
let ans = 0;
left[0] = 1;
right[0] = 1;
for(let i = 1; i < arr.length; i++){
    if(arr[i] > arr[i-1]){
        left[i] = left[i-1] + 1;
    }else{
        left[i] = 1;
    }
    //left[i] = computeLeft(i, arr);
}
for(let i = arr.length - 1; i >= 0; i--){
    if(arr[i] < arr[i+1]){
        right[i] = right[i+1]+1;
    }else{
        right[i] = 1;
    }
    //right[i] = computeRight(i, arr);
}
for(let i = 1 ; i < arr.length-1; i++){
    if(arr[i-1] <  arr[i+1]){
        let sum = left[i-1] + right[i+1];
        if(sum > ans){
            ans = sum;
        }
    }
}

print(ans+1);