## Introduction

This blog will discuss the solution to this problem to find the Longest subsequence such that the difference between adjacent elements is K.For example consider this array[] = {2, 5, 7, 5, 3, 0, 1}, K =2 here the longest subsequence with the difference between adjacent equal to K is [5, 7, 5, 3, 1].

### Problem Statement

We are given an array arr[] of size N, and our task is to find the longest subsequence such that the absolute difference between adjacent elements in K. So before we deep dive into the answer, we should look at some examples to understand the problem better.

### Some Examples

**Example 1:**

**Input:**

`arr[] = [1, 3, 1, 5, 4], K = 2`

**Output:**

`3`

**Explanation:**

The longest subsequence with the difference between the adjacent elements as 2 is [1, 3, 1]

**Example 2:**

**Input:**

`arr[] = [2, 7, 4, 5, 1, 4, 9] K = 3`

**Output:**

`4 `

## Approach

- To solve this problem, to find the longest subsequence such that the difference between adjacent elements is K, we will use dynamic programming.
- We will store the length of the longest subsequence, which has a difference K between the adjacent elements after including the current element.
- We will create an unordered map m where m[i] will represent the maximum length of the subsequence, which includes the integer i.
- The relation to finding the maximum length subsequence is given below:

**m[i] = 1 + max(m[i â€“ K], m[i + K])**

- We will store the max value of m[i] in another variable named ans and when the loop is over we will return the variable.

### Pseudocode

```
int longestSubsequenceInArray(vector<int> &arr, int K){
unordered_map<int, int> m;
int ans = 1;
for (auto x: arr)
{
m[x] = 1;
m[x] = 1 + max(m[x + K], m[x - K]);
ans = max(ans, m[x]);
}
return ans;
}
```