최장 증가 부분 수열(LIS) 알고리즘

최장 증가 부분 수열(LIS) 알고리즘

글. 수알치 오상문 

 

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

n개 길이 배열의 일부 원소 중에서 만든 부분 수열 중, 각 원소가 이전 원소보다 크고, 길이가 최대인 부분 수열

 

{ 6, 2, 5, 1, 7, 4, 8, 3} 배열의 LIS는 { 2, 5, 7, 8 }이고 길이는 4

 

일반적으로 DP를 이용하여 해결한다.

 

파이썬 코드는 다음과 같다.

length[i]는 i번째 인덱스 기준으로 최장 증가 부분 수열의 길이를 의미한다.

data = [6, 2, 5, 1, 7, 4, 8, 3]
# LIS 알고리즘 구현
length = [1] * n    # 최소한 자기 자신일 때는 길이 1
for i in range(1, n):   # i = 1~n-1
    for j in range(i):  # j = 0~i-1
        if data[i] > data[j]: # 기준 위치 i보다 작은 값이면...  
            length[i] = max(length[i], length[j] + 1)
                         # 현재 값과 j 위치 값+1 중에서 큰 값으로 갱신
print(max(length))