Given a set of integers in an array A[] of size n , write a program to find the length of the longest arithmetic subsequence in A. More formally, find longest sequence of indices, 0 <= i1 < i2 < … < ik <= n-1 such that sequence A[i1], A[i2], …, A[ik] is an Arithmetic Progression.

Problem Note

  • Arithmetic Progression is a sequence in which all the differences between consecutive pairs are the same, i.e sequence P[0], P[1], P[2], …, P[m - 1] of length m is an Arithmetic Progression if and only if P[1] - P[0] == P[2] - P[1] == P[3] - P[2] == … == P[m - 1] - P[m - 2]
  • The common difference can be positive, negative or 0.

Example 1

Input: A[] = [3, 6, 9, 12]
Output: 4
Explanation: [3, 6, 9, 12] form an arithmetic progression.

Example 2

Input: A[] = [9, 4, 7, 2, 10]
Output: 3
Explanation:[4, 7, 10] form an arithmetic progression.