10057 가장 긴 증가하는 부분수열 Silver II

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분수열(LIS)의 길이를 구하는 프로그램을 작성하시오.

부분수열은 원래 수열에서 일부 원소를 골라 순서를 유지한 것이며, 증가하는 부분수열은 원소가 순증가하는 것을 말한다.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에 수열을 이루는 N개의 정수가 주어진다. 각 정수는 1 이상 1,000 이하이다.

출력

가장 긴 증가하는 부분수열의 길이를 출력한다.

6
10 20 10 30 20 50

4