인프런 커뮤니티 질문&답변

이진혁

작성한 질문수

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

3. 최대부분증가수열(LIS)

강의 코드에 반례가 있습니다.

작성

474

-1

입력이 [5, 2, 4, 6, 7]로 주게되면 5, 6, 7 를 뽑아내어 길이가 3인 최대 부분 증가수열을 만들 수 있습니다.

하지만 강의코드에서 위와 같이 입력을 주게되면 출력이 4가 나옵니다.

반례의 경우에도 올바른 출력이 나오도록 수정해보았습니다.

확인부탁드립니다.

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(arr){  
               let answer = 0;
               let n = arr.length;
               let dy = Array.from({length:n}, ()=>0);
               dy[0] = 1;
               let max = 0;

               for(let i=1; i<n; i++){
                   if(arr[i] > arr[max]){
                       dy[i] = dy[i-1]+1;
                       max = i;
                   }
                   else dy[i] = dy[i-1];
                   answer = Math.max(answer, dy[i]);
               }
               
               return answer;
            }

            let arr=[5,2,4,6,7];
            console.log(solution(arr));
        </script>
    </body>
</html>