[Algorithms] Longest Increasing Subsequence | 최장 증가 부분 수열

Longest Increasing Subsequence (LIS)

 

최장 증가 부분 수열

 

 

 

- 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거하여 부분수열을 만들 수 있는데,
  이때 만들어지는 다양한 부분수열들 중 오름차순으로 정렬된 부분수열들 중에서 길이가 가장 긴 부분수열을 LIS라 한다.

- 어떤 임의의 수열에 대해 LIS는 하나 이상 존재한다.

 

---

Mechanism (원리)

※ 이 문제의 답은 Optimal Substructure를 갖고 있으므로, Dynamic Programming (URL) 기법을 적용해 볼 수 있다.

 

[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍

 

 

---

Implementation (구현)

 

* Pseudo Code

P = array of length N
M = array of length N + 1
M[0] = -1 // undefined so can be set to any value

L = 0
for i in range 0 to N-1:
    // Binary search for the smallest positive l ≤ L
    // such that X[M[l]] > X[i]
    lo = 1
    hi = L + 1
    while lo < hi:
        mid = lo + floor((hi-lo)/2) // lo <= mid < hi
        if X[M[mid]] > X[i]
            hi = mid
        else: // if X[M[mid]] <= X[i]
            lo = mid + 1

    // After searching, lo == hi is 1 greater than the
    // length of the longest prefix of X[i]
    newL = lo

    // The predecessor of X[i] is the last index of 
    // the subsequence of length newL-1
    P[i] = M[newL-1]
    M[newL] = i
    
    if newL > L:
        // If we found a subsequence longer than any we've
        // found yet, update L
        L = newL

// Reconstruct the longest increasing subsequence
// It consists of the values of X at the L indices:
// ...,  P[P[M[L]]], P[M[L]], M[L]
S = array of length L
k = M[L]
for j in range L-1 to 0:
    S[j] = X[k]
    k = P[k]

return S

 

 

---

Reference: Wikipedia, "Longest increasing subsequence", 2022.09.06 검색, URL.