inflearn logo
강의

講義
知識共有

JavaScriptアルゴリズムの問​​題プール入門（コーディングテストに比べ）

3. 最大部分増加数列(LIS)

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

478

wlswl24352605

投稿した質問数 2

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

javascript 코테 준비 같이 해요!

回答 2

2

log

말씀하신 경우는 반례가 아닌거 같습니다. 

5, 2, 4, 6, 7 에서 LIS 는 5, 8, 7 이 아닌 2, 4, 6, 7 입니다.

0

wjdgksak

반례 또있습니다.

입력
1
1
출력
0

정답출력
1

검토 부탁드립니다.
감사합니다.

continue를 사용하는 이유

0

76

2

정렬 가능 여부 판단하기

0

63

2

알고리즘 학습법 관련해서 질문드립니다.

0

81

1

코드 리뷰 부탁드립니다!

0

88

1

indexOf를 사용해서 풀어보았습니다 !!

0

67

1

저는 이런식으로 구현 해보았습니다 !!

0

63

1

12,13,14 강의 소리만 나오고 검은 화면입니다

0

97

3

반복문 최소화하고 indexOf 사용해서 풀어봤습니다

0

61

1

영상 보기 전에 직접 풀어봤습니다.

0

71

1

섹션1의 17번문제 이 풀이로 풀어도 될까요?

0

133

2

정규표현식으로 처리해도 상관없나요 ?

0

119

2

3칸씩 건너뛸 수 있을 경우

0

124

2

강의에 대해 질문있습니다.

0

133

2

Object와 Set을 이용해 풀어봤습니다.

0

116

2

이렇게 해도 되나요?

0

102

2

선생님 중복 단어나 중복관련 문제들은 set을 이용하면 좋을것 같습니다.

0

144

2

이렇게 풀어도 괜찮을까요?

0

136

1

이렇게 풀어도 괜찮을까요?

0

112

1

모든 아나그램 찾기에서 시간복잡도

0

98

1

코드리뷰 부탁드립니다.

0

129

1

for loop 탈출은 return 문으로 해도 되지 않나요?

0

130

1

투포인트알고리즘으로 풀어봤습니다.

0

139

0

코드 리뷰 부탁드립니다.

0

116

1

코드 맞게 작성한 거 아닌가여??

0

143

1