Longest subsequence forming an Arithmetic Progression ( AP ) | C ++ program for the above approach ; Function that finds the longest arithmetic subsequence having the same absolute difference ; Stores the length of sequences having same difference ; Stores the resultant length ; Iterate over the array ; Update length of subsequence ; Return res ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lenghtOfLongestAP ( int A [ ] , int n ) { unordered_map < int , unordered_map < int , int > > dp ; int res = 2 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = i + 1 ; j < n ; ++ j ) { int d = A [ j ] - A [ i ] ; dp [ d ] [ j ] = dp [ d ] . count ( i ) ? dp [ d ] [ i ] + 1 : 2 ; res = max ( res , dp [ d ] [ j ] ) ; } } return res ; } int main ( ) { int arr [ ] = { 20 , 1 , 15 , 3 , 10 , 5 , 8 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << lenghtOfLongestAP ( arr , N ) ; return 0 ; }