문제1365--증감 수열

1365: 증감 수열

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 455  통과: 101
[제출] [채점기록] [묻고답하기]

문제 설명

증감 수열이란, 수열의 원소를 앞에서부터 고려할 때 증가/감소가 교차되는 수열을 의미한다 (감소/증가로 시작해도 상관없다).

주어진 수열의 가능한 모든 부분 증감 수열들 가운데 가장 긴 것의 길이를 찾아라. 부분 수열이 연속된 원소로 구성될 필요는 없다.

 

길이가 $N$인 수열 $A[0..N-1]$가 증감 수열일 조건은 임의의 인덱스 $i$ $(0 \leq i \le N - 2)$ 에 대해 수학적으로 정의하면 다음과 같다 :)

$(A[i + 1] - A[i]) * (A[i + 2] - A[i + 1]) \le 0$

(문제랑은 관련이 없음)

 

입력 설명

첫 행에는 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 행에는 수열의 길이 $N (1 \leq N \leq 1000)$ 이 주어진다.

다음 $N$개의 행에 걸쳐 한 행에 하나씩 수열의 원소가 차례로 주어진다. 각 원소는 $-100$ 이상 $100$ 이하이다.

출력 설명

 각 테스트 케이스에 대해 부분 증감 수열의 최대 길이를 한 행에 하나씩 출력한다.

입력 예시 Copy

2
4
1
5
3
-1
4
5
1
3
-1

출력 예시 Copy

3
4

출처/분류