최장 증가 부분수열

1 개요

최장 증가 부분수열 문제, 최장 증가 부분수열

longest increasing subsequence problem, longest increasing subsequence

• 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제
• 여기서의 부분 수열은 연속적이거나 유일할 필요는 없음
• 입력수열의 길이가 n일 때 [math]\displaystyle{ O(n\log n) }[/math] 시간에 풀이 가능

2 같이 보기

• 부분수열
• 최장 공통 부분수열

3 참고

• 위키백과 "최장 증가 부분수열"
• 영어 위키백과 "Longest increasing subsequence"
• 다음백과 "최장 증가 부분수열"
• 네이버백과 "최장 증가 부분수열"