# Longest subsequence such that difference between adjacents is one | Set 2

Given an array of size n. The task is to find the longest subsequence such that difference between adjacents is one. Time Complexity of O(n) is required.

Examples:

```Input :  arr[] = {10, 9, 4, 5, 4, 8, 6}
Output :  3
As longest subsequences with difference 1 are, "10, 9, 8",
"4, 5, 4" and "4, 5, 6".

Input :  arr[] = {1, 2, 3, 2, 3, 7, 2, 1}
Output :  7
As longest consecutive sequence is "1, 2, 3, 2, 3, 2, 1".
```

Method 1: Previously an approach having time complexity of O(n2) have been discussed in this post.

Method 2 (Efficient Approach): The idea is to create a hash map having tuples in the form (ele, len), where len denotes the length of the longest subsequence ending with the element ele. Now, for each element arr[i] we can find the length of the values arr[i]-1 and arr[i]+1 in the hash table and consider the maximum among them. Let this maximum value be max. Now, the length of longest subsequence ending with arr[i] would be max+1. Update this length along with the element arr[i] in the hash table. Finally, the element having the maximum length in the hash table gives the longest length subsequence.

## C++

 `// C++ implementation to find longest subsequence  ` `// such that difference between adjacents is one ` `#include ` `using` `namespace` `std; ` `   `  `// function to find longest subsequence such ` `// that difference between adjacents is one ` `int` `longLenSub(``int` `arr[], ``int` `n) ` `{ ` `    ``// 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 ` `    ``unordered_map<``int``, ``int``> um; ` `      `  `    ``// to store the longest length subsequence ` `    ``int` `longLen = 0; ` `      `  `    ``// traverse the array elements ` `    ``for` `(``int` `i=0; i

## Python3

 `# Python3 implementation to find longest  ` `# subsequence such that difference between  ` `# adjacents is one  ` `from` `collections ``import` `defaultdict ` ` `  `# function to find longest subsequence such  ` `# that difference between adjacents is one  ` `def` `longLenSub(arr, n): ` ` `  `    ``# 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  ` `    ``um ``=` `defaultdict(``lambda``:``0``) ` `    ``longLen ``=` `0` `    ``for` `i ``in` `range``(n): ` ` `  `        ``# / initialize current length  ` `        ``# for element arr[i] as 0  ` `        ``len1 ``=` `0` ` `  `        ``# if 'arr[i]-1' is in 'um' and its length  ` `        ``# of subsequence is greater than 'len'  ` `        ``if` `(arr[i ``-` `1``] ``in` `um ``and`  `            ``len1 < um[arr[i] ``-` `1``]): ` `            ``len1 ``=` `um[arr[i] ``-` `1``] ` ` `  `        ``# f 'arr[i]+1' is in 'um' and its length  ` `        ``# of subsequence is greater than 'len'    ` `        ``if` `(arr[i] ``+` `1` `in` `um ``and`  `            ``len1 < um[arr[i] ``+` `1``]): ` `            ``len1 ``=` `um[arr[i] ``+` `1``] ` ` `  `        ``# update arr[i] subsequence  ` `        ``# length in 'um'      ` `        ``um[arr[i]] ``=` `len1 ``+` `1` ` `  `        ``# update longest length  ` `        ``if` `longLen < um[arr[i]]: ` `            ``longLen ``=` `um[arr[i]] ` ` `  `    ``# required longest length ` `    ``# subsequence  ` `    ``return` `longLen ` ` `  `# Driver code ` `arr ``=` `[``1``, ``2``, ``3``, ``4``, ``5``, ``3``, ``2``] ` `n ``=` `len``(arr) ` `print``(``"Longest length subsequence ="``, ` `                  ``longLenSub(arr, n)) ` ` `  `# This code is contributed by Shrikant13 `

Output:

```Longest length subsequence = 6
```

Time Complexity: O(n).
Auxiliary Space: O(n).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Hash cpp-unordered_map Arrays Hash

code

load comments