최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 주어진 수열에서 오름차순으로 정렬된 부분 수열 중에서 가장 긴 것을 의미한다. 부분 수열은 원래 수열의 원소들을 선택하되 순서를 유지하면서 일부 원소를 생략하여 만들 수 있는 시퀀스이다.

최장 증가 부분 수열을 찾는 문제는 컴퓨터 과학과 알고리즘 분야에서 중요한 주제로, 여러 가지 응용 사례가 있다. 예를 들어, 데이터 압축, 최근 데이터의 트렌드 분석, 그리고 동적 프로그래밍의 연습 문제 등에서 활용된다.

최장 증가 부분 수열을 구하는 알고리즘은 일반적으로 두 가지 방식으로 나뉜다. 첫 번째는 동적 프로그래밍(dynamic programming)을 이용하는 방법으로, O(n^2)의 시간 복잡도로 최장 증가 부분 수열의 길이를 계산할 수 있다. 이 방법은 각 원소에 대해 그 이전에 있는 원소들과 비교하여 증가하는 수열을 판별하는 방식이다.

두 번째는 이분 탐색(binary search)을 이용한 방법으로, O(n log n)의 시간 복잡도로 구현할 수 있다. 이 방법은 현재까지 발견한 최장 길이의 증가 부분 수열을 유지하며 새로운 원소를 sequential하게 추가하거나 교체하는 방식으로 진행된다.

최장 증가 부분 수열 문제는 NP-hard 문제는 아니지만, 실제로 많은 응용이 있는 알고리즘 문제 중 하나로, 다양한 최적화 기술을 통해 더 효율적인 해결책이 개발되기도 하였다.