[DP] 최장 증가 부분 수열

문제

길이 $N$인 수열에서 엄격히 증가하는 부분 수열(원소를 골라 순서를 유지) 중 가장 긴 것의 길이를 구하라.

접근

$dp[i]$를 "$i$번 원소로 끝나는 증가 부분 수열의 최대 길이"로 두면 $O(N^2)$로 풀린다. 더 빠르게는, 길이별로 "마지막 원소의 최솟값"을 배열 tails로 관리하고 새 값마다 이진 탐색으로 자리를 찾으면 $O(N \log N)$이다. 엄격 증가이므로 tails에서 새 값 이상인 첫 자리를 찾아 덮어쓴다.

입출력 예시

입력:
6
10 20 10 30 20 50
출력: 4