[BOJ] 14003번: 가장 긴 증가하는 부분 수열 5

https://www.acmicpc.net/problem/14003

가장 긴 증가하는 부분 수열은 세그먼트 트리 혹은 Binary indexed tree 혹은 binary search를 이용해 $O(NlgN)$에 구현할 수 있습니다. 아무래도 binary search가 구현이 쉬운데, 이 경우에는 수열을 복원하는 것이 조금 문제입니다. 다양한 방법이 있지만 $myLIS[i]$를 $A[0~i]$에서의 LIS 길이로 두고 주어진 수열에서 LIS의 길이를 len이라고 할 때 $i = N-1$부터 확인하면서 $myLIS[i] = len$인 $i$를 출력하고, 이후 $myLIS[i] = len-1$인 $i$를 출력하고 ,... , $myLIS[i] = 1$인 $i$를 출력하면 됩니다.

http://mygumi.tistory.com/303 를 참고하는 것을 추천합니다.

https://github.com/blisstoner/BOJ/blob/master/14003.cpp