LIS

LIS는 최장 증가 부분 수열로, 어떤 수열에서 점점 증가하는 부분 수열중 가장 긴것을 찾는 알고리즘이다.

이 수열 자체를 찾을 수 있는 방법과, 길이만 알 수 있는 방법이 있고, 둘다 O(nlogn)으로 해결이 가능하다. 전자는 구현이 복잡해서 후자로 구현해보았다.

후자는 이진탐색과 새로운 배열로 구현이 가능하다.

소스