Longest Arithmetic Subsequence with Given Difference
Difficulty: Hard.
Given an array of integers and a positive integer k, find the length of the longest arithmetic progression with common difference k. Ignore duplicates.
Example
Input
arr = [8, 1, -1, 0, 3, 6, 2, 4, 5, 7, 9]
k = 2
Output
6
Explanation
Remove duplicates (none here) and consider the set of unique elements:
We seek the longest arithmetic progression with difference k=2.
Starting at -1 gives the sequence [-1,1,3,5,7,9] of length 6.
No other starting point yields a longer progression, so the result is 6.
Input Format
- The first line contains an integer n denoting the number of elements in the array.
- The next n lines contains an integer denoting elements in the array.
- The last line contains the value for integer k.
Example
11 → number of elements
8 → elements of the array
1
-1
0
3
6
2
4
5
7
9
2 → value of k
Constraints
- 0 <= arr.length <= 100000
- -10^9 <= arr[i] <= 10^9 for each 0 <= i < arr.length
- 1 <= k <= 10^9
- Duplicates may appear in arr but should be ignored when forming the progression
Output Format
- A single integer denoting the length of the longest arithmetic progression.
Sample Input 0
0
5
Sample Output 0
0
Sample Input 1
1
42
7
Sample Output 1
1Consideration:
1. Sort the vector.
2. Each element could be selected to be start element.
3. While searching for the next same difference value, you could break the loop if the difference with current value is larger than k.
4. Skip next element searching if that difference with current element equals to k. (Already calculated.)
5. Very important: If don't apply this point, it may become timeout for test case#13.
When the rest number of the vector is smaller than longest length of same k-difference sequence we had found, just skip the rest check. It's because no chance to get another longer length for next search.
Code:
/*
* Complete the 'findLongestArithmeticProgression' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER_ARRAY arr
* 2. INTEGER k
*/
int findLongestArithmeticProgression(vector<int> arr, int k) {
sort(arr.begin(), arr.end());
int longest_length=1;
int cur_length;
int n = arr.size();
if (n==0) return 0;
if (n==1) return 1;
int pv;
for (int i=0;i<n-longest_length;i++) {
cur_length=1;
pv = arr[i];
if ( (i>0) && ((arr[i]-arr[i-1])==k) ) continue;
for (int j=i+1;j<n;j++) {
if ((arr[j]-pv)==k) {
//cout << "pv = " << pv << "\n";
//cout << "cv = " << arr[j] << "\n";
//cout << "j = " << j << "\n";
cur_length++;
//cout << "cur_length = " << cur_length << "\n";
pv = arr[j];
}
else if (((arr[j]-pv) > k)) {
break;
}
}
if (cur_length > longest_length) {
longest_length = cur_length;
}
}
return longest_length;
}
