# Maximum length subsequence with difference between adjacent elements as either 0 or 1 | Set 2

Given an array of n integers. The problem is to find maximum length of the subsequence with difference between adjacent elements in the subsequence as either 0 or 1. Time Complexity of O(n) is required.

Examples:

```Input : arr[] = {2, 5, 6, 3, 7, 6, 5, 8}
Output : 5
The subsequence is {5, 6, 7, 6, 5}.

Input : arr[] = {-2, -1, 5, -1, 4, 0, 3}
Output : 4
The subsequence is {-2, -1, -1, 0}.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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, arr[i] 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 maximum length subsequence.

## C++

 `// C++ implementation to find maximum length ` `// subsequence with difference between adjacent  ` `// elements as either 0 or 1 ` `#include ` `using` `namespace` `std; ` `  `  `// function to find maximum length subsequence  ` `// with difference between adjacent elements as ` `// either 0 or 1 ` `int` `maxLenSub(``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 maximum length subsequence ` `    ``int` `maxLen = 0; ` `     `  `    ``// traverse the array elements ` `    ``for` `(``int` `i=0; i

## Python3

 `# Python3 implementation to find maximum  ` `# length subsequence with difference between  ` `# adjacent elements as either 0 or 1  ` `from` `collections ``import` `defaultdict ` ` `  `# Function to find maximum length subsequence with  ` `# difference between adjacent elements as either 0 or 1  ` `def` `maxLenSub(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``) ` `     `  `    ``# to store the maximum length subsequence  ` `    ``maxLen ``=` `0` `     `  `    ``# traverse the array elements  ` `    ``for` `i ``in` `range``(``0``, n):  ` `     `  `        ``# initialize current length  ` `        ``# for element arr[i] as 0  ` `        ``length ``=` `0` `         `  `        ``# if 'arr[i]-1' is in 'um' and its length of  ` `        ``# subsequence is greater than 'len'  ` `        ``if` `(arr[i]``-``1``) ``in` `um ``and` `length < um[arr[i]``-``1``]: ` `            ``length ``=` `um[arr[i]``-``1``]  ` `         `  `        ``# if 'arr[i]' is in 'um' and its length of  ` `        ``# subsequence is greater than 'len'  ` `        ``if` `arr[i] ``in` `um ``and` `length < um[arr[i]]:  ` `            ``length ``=` `um[arr[i]]  ` `             `  `        ``# if 'arr[i]+1' is in 'um' and its length of  ` `        ``# subsequence is greater than 'len'   ` `        ``if` `(arr[i]``+``1``) ``in` `um ``and` `length < um[arr[i]``+``1``]:  ` `            ``length ``=` `um[arr[i]``+``1``]  ` `         `  `        ``# update arr[i] subsequence length in 'um'  ` `        ``um[arr[i]] ``=` `length ``+` `1` `         `  `        ``# update maximum length  ` `        ``if` `maxLen < um[arr[i]]:  ` `            ``maxLen ``=` `um[arr[i]]  ` `     `  `    ``# required maximum length subsequence  ` `    ``return` `maxLen ` ` `  `# Driver program to test above  ` `if` `__name__ ``=``=` `"__main__"``:  ` ` `  `    ``arr ``=` `[``2``, ``5``, ``6``, ``3``, ``7``, ``6``, ``5``, ``8``]  ` `    ``n ``=` `len``(arr)  ` `    ``print``(``"Maximum length subsequence ="``, maxLenSub(arr, n)) ` `     `  `# This code is contributed by Rituraj Jain `

Output:

```Maximum length subsequence = 5
```

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

Thanks to Neeraj for suggesting the above solution in the comments of this post.

Hash Hash