Longest subsequence such that difference between adjacents is one | Set 2 | C # 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 ' ; if ' 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 program to test above
using System ; using System . Collections . Generic ; class GFG { static int longLenSub ( int [ ] arr , int n ) { Dictionary < int , int > um = new Dictionary < int , int > ( ) ; int longLen = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int len = 0 ; if ( um . ContainsKey ( arr [ i ] - 1 ) && len < um [ arr [ i ] - 1 ] ) len = um [ arr [ i ] - 1 ] ; if ( um . ContainsKey ( arr [ i ] + 1 ) && len < um [ arr [ i ] + 1 ] ) len = um [ arr [ i ] + 1 ] ; um [ arr [ i ] ] = len + 1 ; if ( longLen < um [ arr [ i ] ] ) longLen = um [ arr [ i ] ] ; } return longLen ; } static void Main ( ) { int [ ] arr = { 1 , 2 , 3 , 4 , 5 , 3 , 2 } ; int n = arr . Length ; Console . Write ( " Longest ▁ length ▁ subsequence ▁ = ▁ " + longLenSub ( arr , n ) ) ; } }