【算法】算法測試題5：牛牛的數列：最長連續子序列

MRZYD 發布于2019-08-23 11:37 / 1904人閱讀

摘要：題目描述鏈接來源牛客網牛牛現在有一個個數組成的數列牛牛現在想取一個連續的子序列并且這個子序列還必須得滿足最多只改變一個數就可以使得這個連續的子序列是一個嚴格上升的子序列牛牛想知道這個連續子序列最長的長度是多少。

題目描述

鏈接：https://www.nowcoder.com/ques...
來源：牛客網

牛牛現在有一個n個數組成的數列,牛牛現在想取一個連續的子序列,并且這個子序列還必須得滿足:最多只改變一個數,就可以使得這個連續的子序列是一個嚴格上升的子序列,牛牛想知道這個連續子序列最長的長度是多少。

輸入描述

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

輸出描述

輸出一個整數,表示最長的長度。

示例1

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

解題思路

分析：這道題目看上去沒法下手，就當學習一個思路吧，首先根據當前數組順著求一遍以每個位置作為結尾的連續最長遞增子序列的長度值，再逆著求解以每個元素作為開頭的連續最長遞增子序列的長度值，然后根據這兩組值來找連接點。具體就拿體重的例子來說，此時數組arr為
7 2 3 1 5 6，我們定義兩個數組left
和right，left數組表示正著求以每個元素作為結尾的最長遞增子序列的長度，而right數組表示逆著以每個元素作為開頭的連續最長遞增子序列的長度值，所以可以知道left[0]=1,表示以7結尾的目前最長的連續遞增子序列的長度值就是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;好了，到此為止兩個輔助的數組已經求出，接下來就要找連接點了，是這樣的，根據題目意思，我們要找一個子序列，而且之多改變一個數就可以形成嚴格的連續遞增子序列，所以我們先盯住數組中2這個數，我們發現以7結尾的最長的連續遞增子序列的長度為left[0],而以3開頭的連續遞增子序列長度為right[2]，這樣，我們其實不用管7和3之間的數到底是多少，是2也好，不是2也好，只要2前面的數7能夠嚴格小于2后面的數3，說明通過改變7和3之間這個數至合適的數值則，這兩部分就可以連成一個連續的嚴格遞增子序列，所有，我們遍歷所有這樣的點，記錄滿足條件的最大的長度再加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（優化）

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]結尾的連續序列長度
let right = new Array(n);//以arr[i]開頭的連續序列長度
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);

云服務器 GPU云服務器算法最大子數列最大連續子串算法最長遞增子序列最長公共子序列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/97220.html

[算法總結] 搞定 BAT 面試——幾道常見的子符串算法題

摘要：第一種方法常規方法。如果不存在公共前綴，返回空字符串。注意假設字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數值為或者字符串不是一個合法的數值則返回。說明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評論0 收藏0
javascript 最長公共子序列

摘要：但不是和的最長公共子序列，而序列和也均為和的最長公共子序列，長度為，而和不存在長度大于等于的公共子序列。最長公共子序列給定序列和，從它們的所有公共子序列中選出長度最長的那一個或幾個。為和的最長公共子序列長度。最長公共子序列（Longest Common Subsequence LCS）是從給定的兩個序列X和Y中取出盡可能多的一部分字符，按照它們在原序列排列的先后次序排列得到。LCS問...

Xufc 2019-08-22 13:52 評論0 收藏0
2019網易互娛數據挖掘實習生筆試部分記錄

摘要：今晚做完了網易互娛數據挖掘實習生的筆試題，雖然大部分的題目都不太記得了。采樣分為上采樣和下采樣。上采樣是把小眾類復制多份下采樣是從大眾類中剔除一些樣本，或者說只從大眾類中選取部分樣本。今晚做完了網易互娛數據挖掘實習生的筆試題，雖然大部分的題目都不太記得了。但是還是有一些印象比較深的坑需要填一下。比起騰訊和字條跳動難度適中，不算很大，字節的筆試掛了。其實這次感覺自己做的也不是挺好哈哈哈...

Meils 2019-07-31 10:15 評論0 收藏0
【算法】算法測試題4：最長公共連續子串

摘要：問題描述鏈接來源牛客網給出兩個字符串可能包含空格找出其中最長的公共連續子串輸出其長度。示例輸入輸出解題思路比較兩個字符串找出的子串是否在中兩個指針和從頭遍歷到尾，找以開頭的子串中最長的在中的子串。問題描述鏈接：https://www.nowcoder.com/ques...來源：牛客網給出兩個字符串（可能包含空格）,找出其中最長的公共連續子串,輸出其長度。輸入描述輸入為兩行...

MockingBird 2019-08-23 11:36 評論0 收藏0
一道算法題：求出異或和為零的最長連續子串

摘要：最近看見一道算法題，本著見題解題的學習心態解決了它，由于目前正在研究正則表達式，所以就從正則的方向入手了題目如下輸入個整數，中間用空格隔開，求出異或和為的最長連續子串。要求輸出子串的長度子串在輸入的數組中的起始位置和結束位置。最近看見一道算法題，本著見題解題的學習心態解決了它，由于目前正在研究正則表達式，所以就從正則的方向入手了：題目如下：輸入N個整數，中間用空格隔開，求出異或和為...

劉玉平 2019-07-30 18:00 評論0 收藏0