LIS를 O(nlogn)시간 내에 해결하는 방법

LIS는 수열 중에서 가장 긴 수열의 길이를 찾는 방법이다.

동적 계획법 해결 방법은 이전에 찾았던 수열의 마지막 값들 중 현재의 위치의 값보다 작으면 그 마지막 값이 가지고 있는 수열의 길이에 1을 더하는 방식이다. 조건에 해당하는 수열 중에서 가장 긴 수열을 선택해야 한다.

기존의 방법은 긴 수열을 찾는데 O(N)의 시간이 걸려 모든 배열의 값을 탐색한 후에는 전체 알고리즘 복잡도는 O(N^2)가 되었다 

하지만 길이 L 인 수열의 마지막 값들 중 최소 값을 저장하는 배열을 둔다고 생각해보자 C[L]

C[]배열은 순 증가하는 그래프가 될 것이다. 

(간단히 설명하자면 C[N]은 C[N-1]의 영향을 받을 것이고 C[N-1]은 현재 길이에서 최소의 값을 가지기 때문에...귀납적으로 설명하면 그렇다. 직감적으로도 그러하고)

만약 나의 현재 위치의 값이 S라면 C[]에서 이분 탐색을 하고 index값을 통해 위치를 반환 할 수 있을 것이다.

출처 - 알고리즘 문제해결 전략