Longest subsequence such that difference between adjacents 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 }
def longestSubseqWithDiffOne ( arr , n ) : NEW_LINE INDENT dp = [ 1 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( ( arr [ i ] == arr [ j ] + 1 ) or ( arr [ i ] == arr [ j ] - 1 ) ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , dp [ j ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT result = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( result < dp [ i ] ) : NEW_LINE INDENT result = dp [ i ] NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 , 3 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print longestSubseqWithDiffOne ( arr , n ) NEW_LINE