There is an array A made of N integers. Your task is to choose as many integers from A as possible so that, when they are put in ascending order, all of the differences between all pairs of consecutive integers are equal.
For example, for A=14,3,5,1,4,4), you could choose 1, 3 and 5 (with differences equal to 2) or 4,4 and 4 (with differences equal to 0).
What is the maximum number of integers that can be chosen?
Write a function:
int solution(int a[], int N);
that, given an array A made of N Integers, returns the maximum number of integers that can be chosen following the rules described above.
Examples:
- For A = [4, 7, 1, 5, 3), the function should return 4. It is possible to choose four integers (7,1,5
and 3). When put in ascending order, the difference between all consecutive integers is 2.
- For A-[12, 12, 12, 15, 101, the function should retum 3. It is optimal to choose all integers with a
value of 12.
- For A-[18, 26, 18, 24, 24, 20, 221, the function should return 5. Five integers (18, 20, 22, 24, 26) can be chosen. Notice that we cannot pick any other integers, even though they occur more than
once.
Assume that:
N is an integer within the range [250]; each element of array A is an integer within the range [1..100).