Longest subsequence such that difference between adjacents is one | Set 2 | Python3 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   ; f ' 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 code
from collections import defaultdict NEW_LINE def longLenSub ( arr , n ) : NEW_LINE INDENT um = defaultdict ( lambda : 0 ) NEW_LINE longLen = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT len1 = 0 NEW_LINE if ( arr [ i - 1 ] in um and len1 < um [ arr [ i ] - 1 ] ) : NEW_LINE INDENT len1 = um [ arr [ i ] - 1 ] NEW_LINE DEDENT if ( arr [ i ] + 1 in um and len1 < um [ arr [ i ] + 1 ] ) : NEW_LINE INDENT len1 = um [ arr [ i ] + 1 ] NEW_LINE DEDENT um [ arr [ i ] ] = len1 + 1 NEW_LINE if longLen < um [ arr [ i ] ] : NEW_LINE INDENT longLen = um [ arr [ i ] ] NEW_LINE DEDENT DEDENT return longLen NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 , 3 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Longest ▁ length ▁ subsequence ▁ = " , longLenSub ( arr , n ) ) NEW_LINE