最大ローカル増分数列

質問する

code

function solution(arr){  
        let answer =0;
        let dy= Array.from({length:arr.length}, ()=> 0);           
        dy[0]=1;
        for(let i=1; i<arr.length; i++){
            let max =0;
            for(let j=i-1; j>=0; j--){
                if(arr[j]<arr[i] && dy[j]>max){
                    max = dy[j]
                }
            }
            dy[i]= max+1;           
            answer = Math.max(answer, dy[i]);
            
        }                
        return answer;
    }

    let arr=[5, 3, 7, 8, 6, 2, 9, 4];
    console.log(solution(arr));

n/a原理

arr[i]の前の数字を探索し,arr[i]より小さいarr[j]を探し出す.

arr[i]未満の数字では、最大数(max)のdy値(dy[j])を見つけ、+1します.

注意事項

なぜmax=0に初期化するのか

前述したようにmaxを0に初期化しないとmax=3になる.
従ってarr[i]=4であり、これよりも小さい数arr[j]のdy[j]=1であるためmax>dy[j]である.
だからdy[i]の値を求めることはできません.