Longest Increasing consecutive subsequence | CPP 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 ; stores the index of elements ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubsequence ( int a [ ] , int n ) { unordered_map < int , int > mp ; int dp [ n ] ; memset ( dp , 0 , sizeof ( dp ) ) ; int maximum = INT_MIN ; for ( int i = 0 ; i < n ; i ++ ) { if ( mp . find ( a [ i ] - 1 ) != mp . end ( ) ) { int lastIndex = mp [ a [ i ] - 1 ] - 1 ; dp [ i ] = 1 + dp [ lastIndex ] ; } else dp [ i ] = 1 ; mp [ a [ i ] ] = i + 1 ; maximum = max ( maximum , dp [ i ] ) ; } return maximum ; } int main ( ) { int a [ ] = { 3 , 10 , 3 , 11 , 4 , 5 , 6 , 7 , 8 , 12 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << longestSubsequence ( a , n ) ; return 0 ; }