R00201
가장 긴 상승 추세
골드 II레이팅
의견: 0
설명
어떤 주식의 \(N\)일간 종가가 \(a_1, a_2, \dots, a_N\) 순서로 주어진다. 애널리스트는 이 주식의 가장 긴 상승 추세의 길이를 알고 싶어 한다.
상승 추세란 날짜 순서를 유지하면서 일부 날을 골라 만든 부분 수열로서, 고른 날들의 종가가 엄격히 증가하는 것을 말한다. 즉 인덱스 \(i_1 < i_2 < \dots < i_k\) 를 골라 \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\) 가 성립하게 할 때, 가능한 가장 큰 \(k\)를 구하여라.
제약
\(1 \le N \le 200{,}000\)
\(1 \le a_i \le 10^9\)
입력 형식
첫째 줄에 날짜의 수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\))이 주어진다.
출력 형식
가장 긴 상승 추세의 길이를 출력한다.
예제 1
입력
6
10 20 10 30 20 50
출력
4설명
10, 20, 30, 50 을 고르면 길이 4의 엄격히 증가하는 부분 수열이 되며, 이보다 긴 것은 없다.
예제 2
입력
5
5 4 3 2 1
출력
1설명
종가가 계속 감소하므로 어떤 한 날만 골라야 한다. 따라서 답은 1이다.
문제 시리즈
골드 III문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
가장 긴 상승 추세
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 긴 상승 추세
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기