빌 장식하기
면접 대비시간 제한1초메모리 제한1024 MB
건물 높이 수열이 주어질 때, 가장 긴 순증가 부분수열의 길이를 구한다.
문제
국제 정보 올림피아드가 일본에서 열리게 되어, 세계 각국의 선수들을 환영하기 위해 공항에서 숙소까지 이어지는 길가의 고층 빌드를 장식하기로 했다. 한 유명한 디자이너에게 디자인을 의뢰했더니, 장식에 사용할 빌드는 공항에서 숙소 방향으로 갈수록 높아져야 한다고 말했다. 즉, 장식에 사용할 빌드의 높이를 공항에 가까운 것부터 순서대로 h1, h2, h3, ... 라고 하면 h1 < h2 < h3 < ... 이어야 한다.
가능한 한 장식을 화려하게 하기 위해, 장식에 사용할 빌드의 수를 최대한 많이 하고 싶다. 모든 빌드의 높이가 입력으로 주어질 때, 사용할 수 있는 빌드 수의 최댓값을 계산하는 프로그램을 작성하라.
입력
입력의 첫째 줄에는 정수 n (1 ≤ n ≤ 1000)이 주어진다. 이는 공항에서 숙소까지의 길에 있는 빌드의 수가 n임을 나타낸다.
다음 n개의 줄에는 각 빌드의 높이가 주어진다. i + 1번째 줄 (1 ≤ i ≤ n)에는 정수 ai (1 ≤ ai ≤ 10000)가 주어진다. 이는 공항에서 i번째 빌드의 높이가 ai임을 나타낸다.
출력
출력은 표준 출력으로 한다. 장식에 사용할 수 있는 빌드 수의 최댓값을 나타내는 정수를 출력하라.
힌트
빌드의 총수가 9이고, 높이가 공항에 가까운 것부터 순서대로 3, 7, 5, 9, 8, 10, 10, 11, 9인 경우를 아래 그림에 나타내었다. 색을 칠한 빌드를 선택하면 장식에 사용하는 빌드의 수를 최대로 할 수 있다. 이때의 최댓값은 5이다.
