Longest Consecuetive Subsequence when only one insert operation is allowed | Function to return the length of longest consecuetive subsequence after inserting an element ; Variable to find maximum value of the array ; Calculating maximum value of the array ; Declaring the DP table ; Variable to store the maximum length ; Iterating for every value present in the array ; Recurrence for dp [ val ] [ 0 ] ; No value can be inserted before 1 , hence the element value should be greater than 1 for this recurrance relation ; Recurrence for dp [ val ] [ 1 ] ; Maximum length of consecutive sequence ending at 1 is equal to 1 ; Update the ans variable with the new maximum length possible ; Return the ans ; Input array
def LongestConsSeq ( arr , N ) : NEW_LINE INDENT maxval = 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT maxval = max ( maxval , arr [ i ] ) NEW_LINE DEDENT dp = [ [ 0 for i in range ( 2 ) ] for i in range ( maxval + 1 ) ] NEW_LINE ans = 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT dp [ arr [ i ] ] [ 0 ] = 1 + dp [ arr [ i ] - 1 ] [ 0 ] NEW_LINE if ( arr [ i ] >= 2 ) : NEW_LINE INDENT dp [ arr [ i ] ] [ 1 ] = max ( 1 + dp [ arr [ i ] - 1 ] [ 1 ] , 2 + dp [ arr [ i ] - 2 ] [ 0 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ arr [ i ] ] [ 1 ] = 1 NEW_LINE DEDENT ans = max ( ans , dp [ arr [ i ] ] [ 1 ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 2 , 1 , 4 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE print ( LongestConsSeq ( arr , N ) ) NEW_LINE