Longest subsequence such that difference between adjacents is one | Set 2 | C ++ implementation to find longest subsequence such that difference between adjacents is one ; function to find longest subsequence such that difference between adjacents is one ; hash table to map the array element with the length of the longest subsequence of which it is a part of and is the last element of that subsequence ; to store the longest length subsequence ; traverse the array elements ; initialize current length for element arr [ i ] as 0 ; if ' arr [ i ] -1' is in ' um ' and its length of subsequence is greater than ' len ' ; if ' arr [ i ] + 1' is in ' um ' and its length of subsequence is greater than ' len ' ; update arr [ i ] subsequence length in ' um ' ; update longest length ; required longest length subsequence ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longLenSub ( int arr [ ] , int n ) { unordered_map < int , int > um ; int longLen = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int len = 0 ; if ( um . find ( arr [ i ] - 1 ) != um . end ( ) && len < um [ arr [ i ] - 1 ] ) len = um [ arr [ i ] - 1 ] ; if ( um . find ( arr [ i ] + 1 ) != um . end ( ) && len < um [ arr [ i ] + 1 ] ) len = um [ arr [ i ] + 1 ] ; um [ arr [ i ] ] = len + 1 ; if ( longLen < um [ arr [ i ] ] ) longLen = um [ arr [ i ] ] ; } return longLen ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 3 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Longest ▁ length ▁ subsequence ▁ = ▁ " << longLenSub ( arr , n ) ; return 0 ; }