Longest subsequence such that difference between adjacents is one | C ++ program to find the longest subsequence such the difference between adjacent elements of the subsequence is one . ; Function to find the length of longest subsequence ; Initialize the dp [ ] array with 1 as a single element will be of 1 length ; Start traversing the given array ; Compare with all the previous elements ; If the element is consecutive then consider this subsequence and update dp [ i ] if required . ; Longest length will be the maximum value of dp array . ; Driver code ; Longest subsequence with one difference is { 1 , 2 , 3 , 4 , 3 , 2 }
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubseqWithDiffOne ( int arr [ ] , int n ) { int dp [ n ] ; for ( int i = 0 ; i < n ; i ++ ) dp [ i ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ i ] == arr [ j ] + 1 ) || ( arr [ i ] == arr [ j ] - 1 ) ) dp [ i ] = max ( dp [ i ] , dp [ j ] + 1 ) ; } } int result = 1 ; for ( int i = 0 ; i < n ; i ++ ) if ( result < dp [ i ] ) result = dp [ i ] ; return result ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 3 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << longestSubseqWithDiffOne ( arr , n ) ; return 0 ; }