Given an array arr[] of size N, and integer K. The task is to find the longest subsequence with the difference between adjacent elements as K
Examples:
Input: arr[] = { 5, 5, 5, 10, 8, 6, 12, 13 }, K = 1
Output: {5, 6}Input: arr[] = {4, 6, 7, 8, 9, 8, 12, 14, 17, 15}, K = 2
Output: {4, 6, 8}
Approach: The task can be solved with the help of dynamic programming. Every element of the array can be considered as the last element of a subsequence. For every element, the idea is to store the length of the longest subsequence having differences between adjacent elements K and the predecessor of the current element on that subsequence. Follow the steps mentioned below to implement the approach.
- Create a map, to store the last occurrence of each element.
- Create an array of pairs dp[] to store the length of longest subsequence ending at an index and the predecessor of that index.
- Now, traverse the array arr[], and for each element arr[i]:
- Search for (arr[i] – K), (arr[i] + K) in the map.
- If they are present, then find out the subsequence with maximum length and store the length and predecessor in dp[i].
- Print the longest subsequence with help of predecessors stored in the array dp[].
Below is the implementation of the above approach.
C++
// C++ program to implement above approach#include <bits/stdc++.h>using namespace std;// Function to find the longest subsequencevector<int> maxSubsequence(vector<int>& arr, int K){ int N = arr.size(); // Declaring the dp[] array and map vector<pair<int, int> > dp(N, { 1, -1 }); unordered_map<int, int> mp; mp[arr[0]] = 1; // Initialise variable to store // maximum length and last index of // the longest subsequence int maxlen = 1, ind = 0; // Loop to find out the longest // subsequence for (int i = 1; i < N; i++) { // If arr[i]-K is present in the part // of array visited till now if (mp.count(arr[i] - K)) { dp[i] = { dp[mp[arr[i] - K] - 1].first + 1, mp[arr[i] - K] - 1 }; } // If arr[i]+K is present in the part // of array visited till now if (mp.count(arr[i] + K)) { if (dp[i].first < dp[mp[arr[i] + K] - 1].first + 1) { dp[i].first = dp[mp[arr[i] + K] - 1].first + 1; dp[i].second = mp[arr[i] + K] - 1; } } // If maximum length increase store // the length and current index as the // last index of longest subsequence if (maxlen < dp[i].first) { maxlen = dp[i].first; ind = i; } mp[arr[i]] = i + 1; } // Declare vector to store the // longest subsequence vector<int> v; // Loop to generate the subsequence while (ind >= 0) { v.push_back(arr[ind]); ind = dp[ind].second; } reverse(v.begin(), v.end()); return v;}// Driver codeint main(){ vector<int> arr = { 4, 6, 7, 8, 9, 8, 12, 14, 17, 15 }; int K = 2; // Calling function to find // longest subsequence vector<int> longSubseq = maxSubsequence(arr, K); for (auto i : longSubseq) cout << i << " "; cout << endl; return 0;} |
Java
// Java program to implement above approachimport java.util.*;class Main { static class Pair<K, V> { public K key; public V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } } // Function to find the longest subsequence public static ArrayList<Integer> maxSubsequence(ArrayList<Integer> arr, int K) { int N = arr.size(); // Declaring the dp[] array and map ArrayList<Pair<Integer, Integer>> dp = new ArrayList<Pair<Integer, Integer>>(N); for (int i = 0; i < N; i++) { dp.add(new Pair<Integer, Integer>(1, -1)); } HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); mp.put(arr.get(0), 1); // Initialise variable to store // maximum length and last index of // the longest subsequence int maxlen = 1, ind = 0; // Loop to find out the longest // subsequence for (int i = 1; i < N; i++) { // If arr[i]-K is present in the part // of array visited till now if (mp.containsKey(arr.get(i) - K)) { dp.set(i, new Pair<Integer, Integer>(dp.get(mp.get(arr.get(i) - K) - 1).getKey() + 1, mp.get(arr.get(i) - K) - 1)); } // If arr[i]+K is present in the part // of array visited till now if (mp.containsKey(arr.get(i) + K)) { if (dp.get(i).getKey() < dp.get(mp.get(arr.get(i) + K) - 1).getKey() + 1) { dp.set(i, new Pair<Integer, Integer>(dp.get(mp.get(arr.get(i) + K) - 1).getKey() + 1, mp.get(arr.get(i) + K) - 1)); } } // If maximum length increase store // the length and current index as the // last index of longest subsequence if (maxlen < dp.get(i).getKey()) { maxlen = dp.get(i).getKey(); ind = i; } mp.put(arr.get(i), i + 1); } // Declare vector to store the // longest subsequence ArrayList<Integer> v = new ArrayList<Integer>(); // Loop to generate the subsequence while (ind >= 0) { v.add(arr.get(ind)); ind = dp.get(ind).getValue(); } Collections.reverse(v); return v; } // Driver code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList(4, 6, 7, 8, 9, 8, 12, 14, 17, 15)); int K = 2; // Calling function to find // longest subsequence ArrayList<Integer> longSubseq = maxSubsequence(arr, K); for (int i : longSubseq) System.out.print(i + " "); System.out.println(); }} |
Python3
# Python program to implement above approach# Function to find the longest subsequencedef maxSubsequence(arr, K): N = len(arr) # Declaring the dp[] array and map dp = [[1, -1] for i in range(N)] mp = {} mp[arr[0]] = 1 # Initialise variable to store # maximum length and last index of # the longest subsequence maxlen = 1 ind = 0 # Loop to find out the longest # subsequence for i in range(1,N): # If arr[i]-K is present in the part # of array visited till now if (arr[i] - K) in mp: dp[i] = [dp[mp[arr[i] - K] - 1][0] + 1, mp[arr[i] - K] - 1] # If arr[i]+K is present in the part # of array visited till now if (arr[i] + K) in mp: if (dp[i][0] < dp[mp[arr[i] + K] - 1][0] + 1): dp[i][0]= dp[mp[arr[i] + K] - 1][0] + 1 dp[i][1] = mp[arr[i] + K] - 1 # If maximum length increase store # the length and current index as the # last index of longest subsequence if (maxlen < dp[i][0]): maxlen = dp[i][0] ind = i mp[arr[i]] = i + 1 # Declare vector to store the # longest subsequence v =[] # Loop to generate the subsequence while (ind >= 0): v.append(arr[ind]) ind = dp[ind][1] v.reverse() return v# Driver codearr = [4, 6, 7, 8, 9, 8, 12, 14, 17, 15 ]K = 2# Calling function to find# longest subsequencelongSubseq = maxSubsequence(arr, K)for i in longSubseq: print(i , end= " ")print()# This code is contributed by Shubham Singh |
Javascript
<script>// JavaScript program to implement above approach// Function to find the longest subsequencefunction maxSubsequence(arr, K){ let N = arr.length // Declaring the dp[] array and map let dp = new Array(N).fill([]).map(()=>[1,-1]) let mp = new Map() mp.set(arr[0], 1) // Initialise variable to store // maximum length and last index of // the longest subsequence let maxlen = 1 let ind = 0 // Loop to find out the longest // subsequence for(let i=1;i<N;i++){ // If arr[i]-K is present in the part // of array visited till now if(mp.has(arr[i] - K)== true) dp[i] = [dp[mp.get(arr[i] - K) - 1][0] + 1, mp.get(arr[i] - K) - 1] // If arr[i]+K is present in the part // of array visited till now if(mp.has(arr[i] + K)){ if (dp[i][0] < dp[mp.get(arr[i] + K) - 1][0] + 1){ dp[i][0]= dp[mp.get(arr[i] + K) - 1][0] + 1 dp[i][1] = mp.get(arr[i] + K) - 1 } } // If maximum length increase store // the length and current index as the // last index of longest subsequence if (maxlen < dp[i][0]){ maxlen = dp[i][0] ind = i } mp.set(arr[i], i + 1) } // Declare vector to store the // longest subsequence let v =[] // Loop to generate the subsequence while (ind >= 0){ v.push(arr[ind]) ind = dp[ind][1] } v.reverse() return v}// Driver codelet arr = [4, 6, 7, 8, 9, 8, 12, 14, 17, 15 ]let K = 2// Calling function to find// longest subsequencelet longSubseq = maxSubsequence(arr, K)for(let i of longSubseq) document.write(i ," ")document.write("</br>")// This code is contributed by shinjanpatra</script> |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ // Function to find the longest subsequence static List<int> MaxSubsequence(List<int> arr, int K) { int N = arr.Count(); // Declaring the dp[] array and map List<(int, int)> dp = Enumerable.Repeat((1, -1), N).ToList(); Dictionary<int, int> mp = new Dictionary<int, int>(); mp[arr[0]] = 1; // Initialise variable to store // maximum length and last index of // the longest subsequence int maxlen = 1, ind = 0; // Loop to find out the longest // subsequence for (int i = 1; i < N; i++) { // If arr[i]-K is present in the part // of array visited till now if (mp.ContainsKey(arr[i] - K)) { dp[i] = (dp[mp[arr[i] - K] - 1].Item1 + 1, mp[arr[i] - K] - 1); } // If arr[i]+K is present in the part // of array visited till now if (mp.ContainsKey(arr[i] + K)) { if (dp[i].Item1 < dp[mp[arr[i] + K] - 1].Item1 + 1) { dp[i] = (dp[mp[arr[i] + K] - 1].Item1 + 1, mp[arr[i] + K] - 1); } } // If maximum length increase store // the length and current index as the // last index of longest subsequence if (maxlen < dp[i].Item1) { maxlen = dp[i].Item1; ind = i; } mp[arr[i]] = i + 1; } // Declare list to store the // longest subsequence List<int> v = new List<int>(); // Loop to generate the subsequence while (ind >= 0) { v.Add(arr[ind]); ind = dp[ind].Item2; } v.Reverse(); return v; } // Driver code static void Main(string[] args) { List<int> arr = new List<int>() { 4, 6, 7, 8, 9, 8, 12, 14, 17, 15 }; int K = 2; // Calling function to find // longest subsequence List<int> longSubseq = MaxSubsequence(arr, K); foreach (var i in longSubseq) Console.Write(i + " "); Console.WriteLine(); }} |
Output
4 6 8
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!