Problemas
증감 수열이란, 수열의 원소를 앞에서부터 고려할 때 증가/감소가 교차되는 수열을 의미한다(감소/증가로 시작해도 상관없다). 수학적으로 정의하면, 길이가 N인 수열 A[0...N-1] 가 증감 수열일 조건은 임의의 인덱스 i (0≤i≤N-2)에 대해 (A[i+1]-A[i])*(A[i+2]-A[i+1])<0 이다. 주어진 수열의 가능한 모든 부분 증감 수열들 가운데 가장 긴 것의 길이를 찾아라. 부분 수열이 연속된 원소로 구성될 필요는 없다.
Entrada
입력의 첫 행에는 수열의 길이 N (1≤N≤1000) 이 주어진다. 다음 N 개의 행에 걸쳐 한 행에 하나씩 수열의 원소가 차례로 주어진다. 각 원소는 -100 이상 100 이하이다.
Salida
입력에 대해 부분 증감 수열의 최대 길이를 한 행에 하나씩 출력한다.
Ejemplo
4
1
5
3
-1
3
Pista
Debes iniciar sesión para escribir código.