LIS 최장 증가 수열

예를들면 3 1 2 4 8 6 7 라는 배열이 있다면 가장 길게 증가하는순으로 정렬된 배열을 말한다

위 예제에선 1, 2, 4, 6, 7 이 가장 긴 증가 부분수열이다.

DP를 이용해 손쉽게 n^2 시간으로 풀수있다.

arr = [3, 1, 2, 4, 8, 6, 7]
n = len(arr)
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

res = max(dp)

하지만 n의크기가 10만정도로 커진다면? 바로 nlgn 으로 풀수있는 알고리즘이 존재한다.

원리는 임의의 배열에 입력이 들어올때마다 정렬된 형태를 유지하며 가장 큰값보다 큰입력이 들어올경우 새로 추가하고

그것이 아니라면 그 배열속의 그값과 작거나 같고 제일비슷한값을 이분탐색(lgN) (lower_bound) 하여 그 인덱스의 값과 교환하는 방식이다.

  위 예제와 같이 3, 1, 2, 4, 8, 6, 7 이라는 배열이 있다면 흐름은 다음과 같다

코드

from bisect import bisect_left

arr = [3, 1, 2, 4, 8, 6, 7]
n = len(arr)
dp = [arr[0]]

for i in range(1, n):
    if dp[-1] < arr[i]:
        dp.append(arr[i])
    else:
        dp[bisect_left(dp, arr[i])] = arr[i]

res = max(dp)

참고로 dp 들은 값들은 실제 최장증가수열이 아니다. 위 예제가 아닌 다른예제에선 실제수열과 다르며 단지 최장증가수열의 길이만 알수있을뿐이다. 

이들의 값을 구해야할 경우 경로를 저장해야한다. 각 입력값이 어느경로를 가리키는지 지정해야하는데

위 예제에선 3, 1이 종료를 가리키며 2는 1을 4는 2를 8과 6은 4를 7은 6을 가리키는데

이때 dp의 마지막값은 실제최장증가수열과 일치하므로 7의 경로를 역추적하면 7-6-4-2-1 이라는 실제최장수열값을 구할수있다.