All problems

Longest Harmonious Subsequence

Easy · hash map

You are given a list of integers nums. You may pick any of its elements (they do not have to be next to each other), keeping them in their original order.

Call a pick harmonious if the largest value you picked is exactly 1 more than the smallest value you picked. Return the largest number of elements in a harmonious pick. If no harmonious pick exists, return 0.

Examples

Example 1

Input: nums = [4, 6, 5, 5, 9, 6, 5]

Output: 5

Take the three 5s and the two 6s. The largest is 6, the smallest is 5, and they differ by exactly 1.

Example 2

Input: nums = [1, 2, 3, 4]

Output: 2

Any two neighbouring values work, for example 1 and 2, but there are no more copies to add.

Example 3

Input: nums = [7, 7, 7]

Output: 0

Every pick has equal largest and smallest values, so the difference is 0, not 1.

Constraints