77. Longest Increasing Subsequence
최장 증가 부분수열(Longest Increasing Subsequence, LIS)은 수열의 부분 수열 중 값이 오름차순으로 나오면서 가장 긴 것을 말한다. 부분 수열은 원래의 수열에서 몇 개의 원소를 제거한 뒤 남는 수열을 의미하며, 연속되지 않는 원소들이 남을 수도 있다. 예를 들어 다음과 같은 수열 $a$가 있을 때 이 수열의 LIS는 $\{2, 4, 6, 7\}$이다. $$a = \{5, {\color{Red}2}, 6, {\color{Red}4}, 8, 3, {\color{Red}6}, {\color{Red}7}\}$$ LIS의 원소들은 단조증가하므로 LIS에는 같은 원소가 두 번 이상 나타날 수 없다. 또한 한 수열에 두 개 이상의 LIS가 존재할 수도 있다. 예를 들어 수열 $a$가 다음과..
