Longest Arithmetic Subsequence

Difficulty: 1800 5000 ms 128 MB

dp

Print the length of the longest subsequence (not necessarily contiguous) forming an arithmetic progression.

Input: the first line has N; the second line has N integers.

Output: the longest arithmetic subsequence length.

Constraints:

• 1 ≤ N ≤ 1000
• |a_i| ≤ 10⁹

Sample Tests

4
3 6 9 12

4

3
1 2 4

2

Read the Editorial