Longest Subsequence With Difference One in java

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);

	}
}