LIS (longest increasing subsequence) 최장 증가 수열

부분수열중 수열의 원소가 증가 하는 형태로만 이루어진 가장 긴 부분수열.

예를 들어 수열 {0, 8, 4, 12, 2, 10, 6, 7, 1}의 LIS는 {0, 4, 6, 7} 또는 {0, 2, 6, 7}이 있다.

LIS를 구하는 Algorithm은 보통 O(n^2), O(nlogn)이 있다.

O(nlogn) 방법 (end = 배열의 마지막 원소, val = 새로 들어오는 원소)

1. 배열에 아무것도 없을 때: 우선 하나 추가한다.
2. 만약 end가 val보다 작다면 val을 배열의 마지막 부분에 추가
3. 만약 val이 end보다 작다면 배열에서 val 보다 크거나 같은 값을 찾아 val을 해당 인덱스에 val로 대체( 한마디로 lower_bound를 찾아서 val과 교체)

ex) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 8

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 4

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 4, 12

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 2, 12

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 2, 10

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 2, 6

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 2, 6, 7

-------------------------------

Arr (1번) {0, 8, 4 ,12, 2, 10, 6 ,7 ,1}

0, 1, 6, 7

------------------------------- 

이렇게 하면 길이 4인 LIS가 하나 나옵니다.

그런데 잘 보시면 1은 포함이 되면 안되는데 포함이 되어 있습니다.

즉, 위 방법으로 알 수 있는것은 단순히 LIS의 길이만을 알수가 있습니다.

LIS의 구성원소의 정보를 알기 위해서는 추가적인 방법이 필요합니다.

(블로그 다음글)

<소스 코드>