You are given an array `nums`

of size `N`

.

Find the length of the longest subsequence of array `nums`

such that the absolute difference between every adjacent element in the subsequence is one.

### Input Format

First line contains the size of array `N`

.

Second line contains n-spaced integers represeting array `nums`

.

### Output Format

Print an integer denoting the length of the longest subsequence of array `nums`

such that the difference between adjacent elements is one.

### Example 1

**Input**

5 4 2 1 5 6

**Output**

3

**Explanation**

The longest subsequence satisfying the condition is {4, 5, 6}.

### Example 2

**Input**

6 -2 2 -1 1 0 -1

**Output**

4

**Explanation**

The longest subsequence satisfying the condition is {-2, -1, 0, -1}. There is another possible subsequence of the same length, i.e., {2, 1, 0, -1}. The length of both the subsequences is 4.

### Constraints

1 <= N <= 10^5

-10^9 <= nums[i] <= 10^9

## Solution:–

import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main (String[] args) throws java.lang.Exception { //your code here Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int A[] = new int[n]; for(int i=0;i<n;i++){ A[i] = sc.nextInt(); } Map<Integer, Integer> mp = new HashMap<>(); int ans = 0; for(int i=0;i<n;i++){ int x = mp.getOrDefault(A[i]+1,0); int y = mp.getOrDefault(A[i]-1,0); mp.put(A[i],Math.max(x,y)+1); ans = Math.max(ans,mp.get(A[i])); } System.out.println(ans); } }

## Add a Comment