Longest subsequence with one difference is { 1 , 2 , 3 , 4 , 3 , 2 }
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubsequence ( int n , int arr [ ] ) { if ( n == 1 ) return 1 ; int dp [ n ] ; unordered_map < int , int > mapp ; dp [ 0 ] = 1 ; mapp [ arr [ 0 ] ] = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( abs ( arr [ i ] - arr [ i - 1 ] ) == 1 ) dp [ i ] = dp [ i - 1 ] + 1 ; else { if ( mapp . count ( arr [ i ] + 1 ) > 0 || mapp . count ( arr [ i ] - 1 ) ) { dp [ i ] = 1 + max ( mapp [ arr [ i ] + 1 ] , mapp [ arr [ i ] - 1 ] ) ; } else dp [ i ] = 1 ; } mapp [ arr [ i ] ] = dp [ i ] ; } return ( * max_element ( dp , dp + n ) ) ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 3 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << longestSubsequence ( n , arr ) ; return 0 ; }