시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB35212410245.536%

문제

길이가 $N$인 수열 $A$가 주어진다. $A$의 부분 수열 중, 등차 수열인 가장 긴 부분 수열의 길이를 출력하는 프로그램을 작성하자.

부분 수열과 등차 수열이 무엇인지 잘 모르는 친구들은 친절한 준서가 준비한 아래 정의를 읽어보도록 하자.

  • 부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.
  • 등차 수열이란 연속한 두 항의 차이가 모두 일정한 수열을 말한다.
  • 예를 들어 $\lbrace1, 3, 5, 7\rbrace$은 연속한 두 항의 차이가 $3-1=5-3=7-5=2$로 일정하므로 등차 수열이다.

입력

첫째 줄에 수열의 길이 $N$이 주어진다. ($1 \leq N \leq 100\,000$)

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq 100$)

출력

첫째 줄에 가장 긴 등차 부분 수열의 길이를 출력한다.

예제 입력 1

8
1 2 3 6 5 3 7 9

예제 출력 1

5

예제 입력 2

5
5 4 3 2 1

예제 출력 2

5

힌트

Python 사용자는 PyPy로 제출하는 것을 권장합니다.

출처

High School > 선린인터넷고등학교 > 제6회 천하제일 코딩대회 예선 E번