1965 상자넣기

앞에서부터 차례대로 증가하는 부분 수열의 개수가 가장 긴 것의 길이를 구하는 문제이다.

이것은 LIS(Longest Increasing Subsequences) 문제로, 직역하자면 최장 증가 부분 수열문제이다. 

이 문제는 O(nlogn)으로 풀이가 가능하다. 이 문제를 해결하는대에도 여러 해법이 있지만, 내가 사용한것은 추가 배열과 이진탐색을 이용하여 문제를 해결하였다.

소스