가장 긴 등차 부분 배열
면접 대비시간 제한20초메모리 제한1024 MB
배열이 주어질 때, 연속한 원소들의 차이가 모두 같은 가장 긴 연속 부분 배열의 길이를 구한다.
문제
등차 배열이란 정수가 두 개 이상 들어 있고 연속한 정수의 차가 모두 같은 배열이다. 예를 들어 [9, 10], [3, 3, 3], [9, 7, 5, 3]은 등차 배열이고, [1, 3, 3, 7], [2, 1, 2], [1, 2, 4]는 등차 배열이 아니다.
Sarasvati는 음이 아닌 정수 N개로 이루어진 배열을 가지고 있다. 배열의 i번째 정수는 Ai이다. Sarasvati는 이 배열에서 연속한 등차 부분 배열 중 가장 긴 것을 고르려고 한다. 가장 긴 연속 등차 부분 배열의 길이를 구하여라.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 따른다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 둘째 줄에는 N개의 정수가 주어진다. i번째 정수는 Ai이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 가장 긴 연속 등차 부분 배열의 길이이다.
제한
- 1 ≤ T ≤ 100.
- 0 ≤ Ai ≤ 109.
힌트
샘플 케이스 #1에서 다음 대괄호 안의 정수들이 가장 긴 연속 등차 부분 배열을 나타낸다: 10 7 [4 6 8 10] 11
샘플 케이스 #2에서는 배열 전체가 등차 배열이므로, 가장 긴 연속 등차 부분 배열은 배열 전체이다.
샘플 케이스 #3에서 가장 긴 연속 등차 부분 배열은 [5, 5, 5](네 번째 정수부터 여섯 번째 정수까지의 부분 배열)이거나 [4, 5, 6](일곱 번째 정수부터 아홉 번째 정수까지의 부분 배열)이다.
샘플 케이스 #4에서 가장 긴 연속 등차 부분 배열은 마지막 여섯 개의 정수이다.