최장 부분 불편 수열 1초 1024MB
문제
수열 b에서 1 ≤ i < j ≤ m 과 j-i≤2 일 때의 bi와 bj가 다르다면 불편 수열이다.
다시 말해, 수열 내에 어느곳에서나 두 수의 거리가 2 이하면서 서로 다르면 불편 수열이다.
(서로 같은 부분이 한 곳이라도 있다면 불편 수열이 아니다.)
수열 a가 주어졌을 때, 수열 a에서 부분 수열 b를 뽑아내어 얻을 수 있는 불편 수열 b의 최대 길이를 구하라.
부분 수열은 원본 수열의 순서를 유지해야 한다.
예를 들어 (1,2,3,4,5) 수열에서 (1,3,5)는 부분 수열이지만 (3,1)은 부분 수열이 아니다.
입력
첫 줄에 테스트 케이스의 수 t(1≤t≤105)가 주어진다.
각 테스트 케이스의 첫 줄에는 수열의 길이 n(1≤n≤2x105)가 주어진다.
그 다음 길이 n의 수열a가 공백을 구분으로 주어진다. 수열에 등장하는 수는 109 이하의 자연수이다.
테스트 케이스에 있는 전체 n의 합은 2x105를 넘지 않음을 보장한다.
출력
각 테스트 케이스의 정답을 줄 별로 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 3점 | ai≤ai+1 |
| #2 | 6점 | n≤8 |
| #3 | 8점 | 모든 테스트 케이스에 있는 n의 합은 500을 넘지 않는다. |
| #4 | 10점 | ai≤3 |
| #5 | 10점 | ai≤10 |
| #6 | 20점 | 모든 테스트 케이스에 있는 n의 합은 10000을 넘지 않는다. |
| #7 | 43점 | 추가 제약 조건 없음. |
예제
3
5
1 2 1 2 1
7
1 2 3 2 1 2 3
8
1 10 10 1 1 100 100 1
2
6
4
첫 번째 테스트 케이스에서 수열 b는 (1,2) 또는 (2,1)가 된다. (1,2,1)은 첫 번째와 세 번째 요소가 같으므로 만족하지 않는다.
두 번째 테스트 케이스에서 수열 b는 (1,2,3,1,2,3)이다.
세 번째 테스트 케이스에서 수열 b는 (1,10,100,1)이다.
로그인해야 코드를 작성할 수 있어요.