Longest Increasing consecutive subsequence | python program to find length of the longest increasing subsequence whose adjacent element differ by 1 ; function that returns the length of the longest increasing subsequence whose adjacent element differ by 1 ; create hashmap to save latest consequent number as " key " and its length as " value " ; stores the length of the longest subsequence that ends with a [ i ] ; iterate for all element ; if a [ i ] - 1 is present before i - th index ; last index of a [ i ] - 1 ; Driver Code
from collections import defaultdict NEW_LINE import sys NEW_LINE def longestSubsequence ( a , n ) : NEW_LINE INDENT mp = defaultdict ( lambda : 0 ) NEW_LINE dp = [ 0 for i in range ( n ) ] NEW_LINE maximum = - sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT if a [ i ] - 1 in mp : NEW_LINE INDENT lastIndex = mp [ a [ i ] - 1 ] - 1 NEW_LINE dp [ i ] = 1 + dp [ lastIndex ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = 1 NEW_LINE DEDENT mp [ a [ i ] ] = i + 1 NEW_LINE maximum = max ( maximum , dp [ i ] ) NEW_LINE DEDENT return maximum NEW_LINE DEDENT a = [ 3 , 10 , 3 , 11 , 4 , 5 , 6 , 7 , 8 , 12 ] NEW_LINE n = len ( a ) NEW_LINE print ( longestSubsequence ( a , n ) ) NEW_LINE