Stepping on Tiles

Interview

Time limit1sMemory limit256 MB

Summary

Given N distinct increasing numbers, find the maximum sum of a 3-or-more element arithmetic subsequence with any common difference, or 0 if none exists.

Level: Medium6 of 10
Topics: Dynamic programming, Hash map, Math, Array
Solved: No attempts yet

Problem

On the way to the competition venue, tiles are laid out in a single row, each marked with a natural number. All of the numbers are distinct, and they are arranged in increasing order from the beginning of the row to the end.

Cheolsu wants to start on one of the tiles and step across several tiles to reach the venue. He steps so that the numbers on the tiles he steps on increase by a fixed natural number $d$ ( $d \ge 1$ ) each time; that is, the numbers he steps on must form an arithmetic progression with common difference $d$ .

Depending on the starting tile and the common difference $d$ , the number of tiles he can step on in a row changes. Cheolsu wants to know the maximum possible sum of the numbers on the tiles he steps on. The run must consist of at least $3$ tiles.

For example, suppose the numbers on the tiles are:

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

Then every way to step on $3$ or more tiles in a row is listed in the table below.

Common difference $d$	Tiles stepped on	Sum
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
5	2, 7, 12, 17	38
6	1, 7, 13	21
6	11, 17, 23	51
7	6, 13, 20	39
8	7, 15, 23	45
9	2, 11, 20	33
11	1, 12, 23	36

The largest sum among them is $17, 20, 23$ ( $d = 3$ ), whose sum is $60$ .

Given the numbers on the tiles in increasing order, write a program that finds the maximum sum of the numbers on tiles that can be stepped on in a run of $3$ or more, as described above. If no such run of $3$ or more tiles exists, print $0$ .

Input

The first line contains the number of tiles $N$ ( $3 \le N \le 3\,000$ ).

The second line contains the $N$ natural numbers written on the tiles in increasing order, separated by spaces. Each number is at most $1\,000\,000$ , and all of them are distinct.

Output

If there is a run of $3$ or more tiles that can be stepped on, print on the first line the maximum sum of the numbers on such a run. If no such run exists, print $0$ .

Examples4

Example 1
Input
```
11
1 2 6 7 11 12 13 15 17 20 23
```
Expected output
```
60
```
Example 2
Input
```
3
1 2 3
```
Expected output
```
6
```
Example 3
Input
```
3
1 2 4
```
Expected output
```
0
```
Example 4
Input
```
5
2 4 6 8 10
```
Expected output
```
30
```