【アルゴリズム】アルゴリズム試験問題5:牛の数列:最長連続サブシーケンス

タイトルの説明
リンク:https://www.nowcoder.com/ques...出典:牛客網
牛は現在n個の数からなる数列を持っていて、牛は今連続的な子配列を取りたいと思っています.そして、この子配列はまだ満たさなければなりません.最大1つの数だけを変えることで、この連続的な子配列を厳格に上昇させることができます.牛はこの連続的な子配列の最長の長さを知りたいと思っています.
説明の入力

      ,         n(1 ≤ n ≤ 10^5),      ;
   n   a_i,          (1 ≤ a_i ≤ 10^9),     。

出力の説明

      ,       。

例1

  
6 
7 2 3 1 5 6
  
5

問題を解く構想.
解析:この問題は手がつけられないように見えるので、一つの考え方を学びましょう.まず、現在の配列に基づいて、各位置を末尾とする連続最長増分サブシーケンスの長さ値を求め、各要素を先頭とする連続最長増分サブシーケンスの長さ値を逆に求め、この2つの値に基づいて接続点を探します.具体的には体重の例では,このとき配列arrは
7 2 3 1 5 6,2つの配列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つの補助配列が求められてきましたが、これから接続点を探します.そうです.テーマの意味によって、私たちはサブシーケンスを探します.そして、1つの数を多く変えることで、厳密な連続増分サブシーケンスを形成することができます.そこで、数グループの2という数を見つめて、7の最後の最長の連続増分サブシーケンスの長をleft[0]とすることを発見しました.3の先頭の連続増分サブシーケンス長をright[2]とすると、7と3の間の数がどれだけであるかにかかわらず、2であるか、2でないかにかかわらず、2の前の数7が2の後の数3よりも厳格に小さくなる限り、7と3の間のこの数を適切な数値に変更することによって、この2つの部分は連続的な厳格増分サブシーケンスに接続することができ、すべて、このような点をすべて巡り,条件を満たす最大の長さを記録してさらに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);