최대 부분 증가수열

문제

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));

원리

• 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]의 값을 구할 수 없게 된다.