가장 긴 등차 부분 배열
면접 대비시간 제한30초메모리 제한1024 MB
배열에서 원소를 최대 하나 바꿀 수 있을 때 만들 수 있는 가장 긴 등차 부분 배열의 길이를 구한다.
문제
Kick Start 2020 Round E에서 Sarasvati는 등차 배열에 대해 배웠다. 이 문제를 풀기 위해 이전 문제를 알 필요는 없다. 등차 배열은 정수가 두 개 이상 들어 있고 이웃한 정수 사이의 차가 모두 같은 배열이다. 예를 들어 [9,10], [3,3,3], [9,7,5,3]은 등차 배열이고, [1,3,3,7], [2,1,2], [1,2,4]는 등차 배열이 아니다.
Sarasvati에게 음이 아닌 정수 N개로 이루어진 배열이 다시 주어진다. 배열의 i번째 정수는 Ai이다. 그녀는 배열에서 원소를 최대 한 개 골라 원하는 정수(음수여도 된다)로 바꿀 수 있다.
배열 A에서 부분 배열이란 A의 연속한 일부분을 말한다. Sarasvati가 원래 배열에서 원소를 최대 한 개 바꿔 만들 수 있는 가장 긴 등차 부분 배열의 길이를 구하시오.
입력
첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 둘째 줄에는 N개의 정수가 주어지며, i번째 정수가 Ai이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 가장 긴 등차 부분 배열의 길이이다.
제한
- 1 ≤ T ≤ 100
- 0 ≤ Ai ≤ 109.
힌트
예제 1에서는 배열 전체가 등차 배열이므로 가장 긴 등차 부분 배열은 배열 전체이다.
예제 2에서 Sarasvati가 세 번째 위치의 수를 5로 바꾸면 배열은 [5,5,5,5,5,5,4,5,6]이 된다. 첫 번째 위치부터 여섯 번째 위치까지의 부분 배열이 가장 긴 등차 부분 배열이다.
예제 3에서 Sarasvati는 마지막 위치의 수를 −1로 바꿔 [8,5,2,−1]을 얻을 수 있다. 이 배열은 등차 배열이다.