상자 넣기
면접 대비시간 제한2초메모리 제한128 MB
주어진 순서의 상자 크기에서 가장 긴 증가 부분수열의 길이를 구합니다.
문제
정육면체 모양의 상자 n개가 앞에서부터 일렬로 놓여 있다. 각 상자에는 크기가 하나씩 주어진다.
앞쪽에 있는 상자의 크기가 뒤쪽에 있는 상자의 크기보다 작을 때에만, 앞쪽 상자를 뒤쪽 상자 안에 넣을 수 있다. 상자의 순서는 바꿀 수 없으므로, 선택한 상자들의 크기는 앞에서부터 보았을 때 엄격히 증가해야 한다.
상자의 크기가 주어질 때, 하나의 중첩된 상자 묶음에 차례대로 넣을 수 있는 상자의 최대 개수를 구하시오.
입력
첫째 줄에 상자의 개수 n (1 <= n <= 1000)이 주어진다.
둘째 줄에 앞에서부터 각 상자의 크기가 공백으로 구분되어 주어진다. 각 크기는 1 이상 1000 이하의 정수이다.
출력
하나의 중첩된 상자 묶음에 넣을 수 있는 최대 상자 개수를 출력한다.