Problem Description
Find the longest Arithmetic Progression in an integer array A of size N, and return its length.
More formally, find longest sequence of indices, 0 < i1 < i2 < … < ik < ArraySize(0-indexed) such that sequence A[i1], A[i2], …, A[ik] is an Arithmetic Progression.
Arithmetic Progression is a sequence in which all the differences between consecutive pairs are the same, i.e sequence B[0], B[1], B[2], …, B[m - 1] of length m is an Arithmetic Progression if and only if B[1] - B[0] == B[2] - B[1] == B[3] - B[2] == … == B[m - 1] - B[m - 2]
Note: The common difference can be positive, negative, or 0.
Problem Constraints
1 <= N <= 1000
1 <= A[i] <= 1e9
Input Format
The first and only argument of input contains an integer array, A.
Output Format
Return an integer, representing the length of the longest possible arithmetic progression.
Example Input
Input 1:
A = [3, 6, 9, 12]
Input 2:
A = [9, 4, 7, 2, 10]
Explanation 1:
[3, 6, 9, 12] form an arithmetic progression.
Explanation 1:
[4, 7, 10] form an arithmetic progression.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified.
Still have a question? Checkout Sample Codes for more details.
