Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible length.
The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant.
I have an O(N^2) solution with DP.
Let dp[i][j] be the answer, if our progression ends with the j-th and i-th element (j <= i; dp[i][i] == 1). Let X[i] be a hash-table (or just an array, if A[i] are small enough, or a map<> if you don’t want a hash table, for an additional O(log N) factor to the complexity), in which you store pairs (A[i]-A[j],j) for j < i; in case of a tie in A[i]-A[j], just the larger j. This table can be constructed easily from dp[i] in linear time.
What happens when you want to know dp[i][j]? It’s just a progression ending with the j-th element, and you append the i-th element, so dp[i][j] == 1+dp[k][j]. The index k is the largest index (<= j) for which A[j]-A[k] == A[i]-A[j], so it’s the second part of the entry (A[i]-A[j],k) in X[j]. If that entry doesn’t exist, then dp[i][j] == 2. Thanks to the hash-table, we can find dp[i][j] in O(1), so we have O(N^2) total complexity.
I find it hard to believe that there could be an algorithm in O(N log N) (note that O-notation means “or better”), so this’ll have to do…
Code (includes excluded :D)
int N, ans =1;
vector<int> A(N); // the input array
vector< vector<int> > dp(N, vector<int>(N,1));
vector< unordered_map<int,int> > X(N);
for(int i =0; i < N; i++) {
for(int j =0; j < i; j++) {
if(X[j].find(A[i]-A[j]) == X[j].end()) {
dp[i][j] =2;
continue;}
int k =X[j][A[i]-A[j]];
dp[i][j] =max(dp[i][j],dp[j][k]+1);}
for(int j =0; j < i; j++) {
X[i][A[i]-A[j]] =j;
ans =max(ans,dp[i][j]);}
}
cout << ans << "\n";I did not get it please give me the exact code for it it will be helpful .thanks
Really? You need a code for DP, which is almost always just about re-writing the formulas mentioned? sigh Ok, I’ll do it.
hey xellos0 can u give the reference for DP as I am not comfortable with DP. Thanks
Sorry, no. I learn to solve problems by solving problems, not by doing theory. But you could do the same and use this problem as a basic idea about how DP works.
My solution takes O[N] time. N is the length of the array.
prev = A[0];
for(i=1;i<N;i++)
{
A[i] = A[i]-prev;
prev = A[i];
}
A[0] = A[1];
A[N] = A[N-1];
Now just find indexs i and j such that all elements A[i] to A[j] are equal and j-i is maximum. This can be done In O[N] time
Then I advise you to read the question again. It asks for an arithmetic subsequence, not substring.
Then i suggest you try and understand my answer before criticising it.
What i am doing above is changing the elements in the array such that each element is the difference between itself and the previous element. Now all you need to do is find the sub array with maximum number of elements which are consecutive and equal. If you need to return the sub array instead of the indexes i and j referring to start and end position of the subarray then i suggest you store the first element of the array in a variable . Using this variable you can get back the previous array .
All this takes O[N] time.
Consecutive equal elements means substring. We don’t want consecutive. And I wasn’t talking about what we need to return, at all.
ya you are right . I thought we have to find consecutive elements.