이번에는 이진 검색을 활용하여 최장 증가 수열의 크기를 구해보자.
C[k]: 길이 k인 증가 수열에 대하여, 0~(k-1)번째 값을 고려하였을 때 k번째에 들어갈 수 있는 가장 작은 값을 C[k]에 저장한다.
이때 이전 알고리즘과는 다르게 LIS 길이는 C[k]에 저장되는 것이 아니라, k 그 자체가 된다!
예를들어 한 학급의 학생들을 키 순으로 정렬한다고 생각해보자.
결과적으로 완성되는 배치는 다음과 같다.
여기서 주의할 점은 line5는 LIS가 아니라는 것이다!!!
이 배열은 오직 LIS의 길이를 구하기 위해 제작된 것이라 이 배열만으로는 정확한 LIS를 알아낼 수 없다.
