최장 증가 부분 수열

컴퓨터 공학에서 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열은 알고리즘을 포함한 수학, 랜덤 행렬 이론, 표현론, 그리고 물리학과 관련된 다양한 분야에서 연구되었다. 최장 증가 부분 수열 문제는, 입력 수열의 길이가 n일 때 O(nlogn)의 시간에 풀이가 가능하다.

같이 보기

• 최장 공통 부분 수열