Tutorialspoint.dev

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 <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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter