New update is available. Click here to update.

Longest Harmonious Subsequence

Posted: 14 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given an array ‘ARR’ of 'N' integers. Your task is to find the longest harmonious subsequence of this array.

A sequence is Harmonious if the difference between the maximum and the minimum of all the elements is exactly 1.

For example
[3, 4, 3, 3, 3, 3, 4] is a harmonic array as the maximum of all the elements is 4 and minimum of all the elements is 3. So, the difference between the maximum and the minimum = 4 - 3 = 1.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains an integer N, which denotes the number of integers in the array ‘ARR’.

The second line of each test case contains 'N' integers of the array ‘ARR’, separated by space.
Output Format:
For each test case, return the size of the longest harmonious subsequence.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1<= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^8

Time Limit: 1 sec