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;
}