Longest subsequence such that the difference between adjacent elements is K

Implementation in C++

// C++ code to find the Longest subsequence such that the difference between adjacent elements is K
#include <bits/stdc++.h>
using namespace std;

// function to find the longest subsequence such that the
// difference between adjacent elements of array is K
int longestSubsequenceInArray(vector<int> &arr, int K)
{
    // to store the length of longest subsequence
    unordered_map<int, int> m;

    // to store the answer
    int ans = 1;

    for (auto x: arr)
    {
        m[x] = 1;

        // taking the maximum of x+Kth element and x-Kth element
        m[x] = 1 + max(m[x + K], m[x - K]);

        ans = max(ans, m[x]);
    }

    // return the answer
    return ans;
}

// Driver Code to find the Longest subsequence such that the difference between adjacent elements is K
int main()
{
    vector<int> arr = {1, 4, 7, 5, 6, 10, 3};
    int K = 3;

    cout << longestSubsequenceInArray(arr, K);
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Input: N = 7 , K = 3
 { 1, 4, 7, 5, 6, 10, 3 }

Output: 4

Complexity Analysis

Time Complexity: O(N)

Since we are doing single traversals, therefore, the time complexity is O(N).

Space Complexity: O(N)

Since we store our answer in a map, the space complexity will be O(N).

Check out this : Longest common subsequence

Frequently asked questions

Q1. What is a Subsequence?

Ans. A subsequence is a sequence that can be derived from a sequence by deleting some elements of that sequence, but the order remains unchanged.

Q2. What is an application of recursion?

Ans. Many well-known sorting algorithms (Quick sort, Merge sort, etc.) use recursion.

Q3. What is a heap?

Ans. Heap is a tree-based data structure. More precisely, it is a particular case of a balanced binary tree that stores the tree’s nodes in a specific order. 

Key takeaways

In this article, we discussed the problem to find the longest subsequence such that the difference between adjacent elements is K. We have discussed its approach based on the priority queue, and we have also discussed the time and space complexities of the approach.

We hope you have understood the problem and now it is your turn to code this problem and other similar problems such as Minimum Subset Sum Difference in your own way.

Until then, Keep Learning and Keep Coding.