**PROBLEM LINK**

**DIFFICULTY**

Easy

**PREREQUISITES**

Dynamic Programming

**PROBLEM IN SHORT**

Output the length of the longest arithmetic sequence possible from the elements of the given array

**SOLUTION**

The first thing to observe is that the order of elements in the array doesn’t matter. Thus, to simplify

things - we just sort the array. This takes O(n log n) time - which is well within the constraints.

A naive approach to the problem would be to look at one pair of elements, take their difference and

find the largest length of AP possible with this difference and the given two elements as the first

two numbers. This will clearly take O(n^3), thus it would fail on the second sub-task.

Now, observe that to define an AP, we require the last two elements and it’s length. The difference

of the last two elements would be the common difference of the AP. Using dynamic programming,

we can compute dp[i][j], where dp[i][j] is length of the AP with the last two elements as a[i] and a[j].

For the recursive function, we need to find the previous element in the AP. This can be done in

O(1) time if we maintain another array, location, where location[i] represents the index of number i

in array a if it exists, otherwise location[i] = -1.

Now, simply, difference = a[j] - a[i], and previousElement = a[i] - difference. Hence, if

location[previousElement] = -1, dp[i][j] = 2, else, dp[i][j] = dp[ location[previousElement] ][i] + 1.

Finally, the answer is simply the maximum dp[i][j] over all i and j.

**TIME COMPLEXITY**

O(n^2)

**EDITORIALIST’s SOLUTION**

```
#include <bits/stdc++.h>
using namespace std;
int dp[2507][2507], n, a[2507], locOfNumber[1000007];
int recur(int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= n)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
else if (i == 0)
return dp[i][j] = 2;
else {
int diff = a[j] - a[i];
int prev = a[i] - diff;
if (prev >= 0) {
int prevInd = locOfNumber[prev];
if ( prevInd != -1 )
return dp[i][j] = recur(prevInd, i) + 1;
else
return dp[i][j] = 2;
}
else
return dp[i][j] = 2;
}
}
int main() {
memset(dp, -1, sizeof(dp));
memset(locOfNumber, -1, sizeof(locOfNumber));
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
locOfNumber[a[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j)
ans = max(ans, recur(i,j) );
}
}
printf("%d", ans);
return 0;
}
```