Longest Arithmetic Progression
Time limit1sMemory limit128 MB
Given up to 2000 nonnegative integers, find the maximum size subset that can be reordered into an arithmetic progression.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Sorting, Hash map
- Solved
- No attempts yet
Problem
You are given N nonnegative integers. Choose any subset of them and arrange the chosen numbers in any order to form an arithmetic progression. Find the maximum possible length of such a progression.
An arithmetic progression is a sequence where the difference between every pair of neighboring terms is constant. The common difference may be negative or 0.
Input
The first line contains the number of integers N (1 ≤ N ≤ 2,000).
Each of the next N lines contains one integer. Every integer is at least 0 and less than 1,000,000,000.
Output
Print the length of the longest arithmetic progression that can be formed.