Longest Consecuetive Subsequence when only one insert operation is allowed | C ++ implementation of above approach ; 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 ; Driver code ; Input array
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LongestConsSeq ( int arr [ ] , int N ) { int maxval = 1 ; for ( int i = 0 ; i < N ; i += 1 ) { maxval = max ( maxval , arr [ i ] ) ; } int dp [ maxval + 1 ] [ 2 ] = { 0 } ; int ans = 1 ; for ( int i = 0 ; i < N ; i += 1 ) { dp [ arr [ i ] ] [ 0 ] = ( 1 + dp [ arr [ i ] - 1 ] [ 0 ] ) ; if ( arr [ i ] >= 2 ) dp [ arr [ i ] ] [ 1 ] = max ( 1 + dp [ arr [ i ] - 1 ] [ 1 ] , 2 + dp [ arr [ i ] - 2 ] [ 0 ] ) ; else dp [ arr [ i ] ] [ 1 ] = 1 ; ans = max ( ans , dp [ arr [ i ] ] [ 1 ] ) ; } return ans ; } int main ( ) { int arr [ ] = { 2 , 1 , 4 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << LongestConsSeq ( arr , N ) ; return 0 ; }