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 <bits/stdc++.h> 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<n; i++) { // initialize current length // for element arr[i] as 0 int len = 0; // if 'arr[i]-1' is in 'um' and its length // of subsequence is greater than 'len' if (um.find(arr[i]-1) != um.end() && len < um[arr[i]-1]) len = um[arr[i]-1]; // if 'arr[i]+1' is in 'um' and its length // of subsequence is greater than 'len' if (um.find(arr[i]+1) != um.end() && len < um[arr[i]+1]) len = um[arr[i]+1]; // update arr[i] subsequence length in 'um' um[arr[i]] = len + 1; // update longest length if (longLen < um[arr[i]]) longLen = um[arr[i]]; } // required longest length subsequence return longLen; } // Driver program to test above int main() { int arr[] = {1, 2, 3, 4, 5, 3, 2}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Longest length subsequence = " << longLenSub(arr, n); return 0; } |
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.
leave a comment
0 Comments