시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 966 104 75 21.994%

문제

정보올림피아드 경시장으로 가는 길에 자연수 값이 적힌 타일이 한 줄로 깔려있다. 철수는 타일에 적힌 자연수 값은 모두 다르고 시작에서부터 증가하는 순서로 깔려있음을 확인하였다.

철수는 임의의 한 타일에서 시작하여 몇 개의 타일을 밟아서 경시장으로 가려고 한다. 단, 타일들에 적힌 숫자가 일정한 자연수만큼 증가하도록 밟으려고 한다.

그러나 철수는 시작하는 위치와 증가하는 값에 따라 연속적으로 밟을 수 있는 타일의 개수가 달라지는 것을 알 수 있었다.

철수는 경시장으로 가면서 위와 같은 방법으로 연속적으로 밟을 수 있는 타일에 적힌 수들의 합 중에서 최대값은 얼마나 될까 계산하여 보기로 하였다. 연속적으로 밟을 수 있는 타일의 개수는 적어도 3개 이상이어야 한다.

예를 들어 타일에 적힌 자연수들의 순서가 다음과 같이 주어졌다고 하자.

1, 2, 6, 7, 11, 12, 13, 15, 17, 20, 23

이 경우 철수가 연속적으로 밟을 수 있는 타일들의 모든 가능한 순서를 열거하면 다음의 표와 같다. 표에 열거한 것 외에 타일을 연속적으로 3개 이상 밟을 수 있는 경우는 없다.

증가하는 값 밟은 타일의 순서
1 11, 12, 13 36
2 11, 13, 15, 17 56
3 17, 20, 23 60
4 7, 11, 15 33
5 1, 6, 11 18
2, 7, 12, 17 38
6 1, 7, 13 21
11, 17, 23 51
7 6, 13, 20 39
8 7, 15, 23 45
9 2, 11, 20 33
11 1, 12, 23 36

따라서 이 예에 대해 철수가 경시장으로 가면서 시작하는 타일을 포함하여 연속적으로 밟을 수 있는 타일에 적힌 수들의 합 중에서 최대값은 60이다.

타일에 적힌 수들이 증가하는 순서로 주어질 때, 철수가 연속적으로 밟을 수 있는 타일이 3개 이상 있는 경우, 그렇게 연속적으로 밟을 수 있는 타일에 적힌 수들의 합 중에서 최대값을 출력하는 프로그램을 작성하시오. 연속해서 타일을 3개 이상 밟을 수 있는 경우가 존재하지 않으면 0을 출력한다.

입력

첫째 줄에는 타일의 개수 N이 주어진다. N은 3 이상 3,000 이하이다. 둘째 줄에는 N개의 타일에 적힌 자연수들이 증가하는 순서로 빈칸을 사이에 두고 주어진다. 타일에 적힌 자연수들은 각각 1,000,000 이하이다.

출력

철수가 연속적으로 3개 이상 밟을 수 있는 타일이 존재하면, 그렇게 연속적으로 밟은 타일에 적힌 수들의 합 중에서 최대값을 첫째 줄에 출력하시오. 연속해서 타일을 3개 이상 밟을 수 있는 경우가 존재하지 않으면 0을 출력한다.

예제 입력

11
1 2 6 7 11 12 13 15 17 20 23

예제 출력

60

힌트

출처

Olympiad > 한국정보올림피아드 > KOI 2008 > 초등부 3번

  • 문제의 오타를 찾은 사람: doju
  • 데이터를 추가한 사람: unused