최장 증가 부분 수열

부분 수열은 순서를 유지하면서 원소를 건너뜁니다. 최장 증가 부분 수열은 그중 엄격하게 증가하는 가장 긴 수열입니다.

부분 배열과 달리 LIS는 연속적일 필요가 없습니다. 더 작은 수들을 건너뛰면서 수열을 계속 늘려도 됩니다.

dp[i]를 인덱스 i에서 끝나는 LIS의 길이라고 합시다. 모든 원소는 그 자체로 길이 1인 부분 수열입니다.

각 i에 대해 앞에 있는 모든 j를 살펴봅니다. a[j]가 더 작으면 수열을 확장하여 dp[i] = max(dp[i], dp[j] + 1)로 갱신합니다.

LIS는 마지막 인덱스가 아니라 어디에서든 끝날 수 있으므로, 결과는 표에서 가장 큰 값입니다.

이중 반복문은 O(n²)의 비용이 듭니다. n이 100000에 가까우면 너무 느려서 시간 제한 초과 판정을 받습니다.

더 빠른 방법은 인내 정렬처럼 각 부분 수열 길이에 대해 가능한 가장 작은 꼬리 값을 목록으로 유지합니다.

각 수에 대해 bisect_left로 꼬리 값들 사이에서 들어갈 위치를 이분 탐색하면 전체 시간은 O(n log n)이 됩니다.

위치가 끝을 지나면 LIS를 늘리기 위해 append합니다. 그렇지 않으면 해당 꼬리 값을 더 작은 값으로 덮어씁니다.

탐색이 끝나면 len(tails)가 LIS의 길이입니다. 목록 자체가 항상 부분 수열인 것은 아니며, 정확한 것은 길이뿐입니다.

비감소 변형에서는 bisect_right로 바꾸어 같은 값도 수열을 확장할 수 있게 합니다.

O(n log n)으로 LIS의 길이를 찾는 방법은 무엇입니까?

이제 LIS를 두 가지 방법으로 해결할 수 있습니다. O(n²) DP는 간단하고, 꼬리 값과 이분 탐색을 결합한 방법은 큰 입력에서도 확장 가능하며 시간 제한을 통과합니다.