Задача: 594. Longest Harmonious Subsequence
Сложность: easy

Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1.

Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.

Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

👨‍💻 Алгоритм:

1⃣Пройдитесь по массиву, создавая словарь для подсчета частоты каждого элемента.

2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.

3⃣Верните максимальную длину гармоничной подпоследовательности.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int FindLHS(int[] nums) {
        var count = new Dictionary<int, int>();
        int res = 0;
        
        foreach (var num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
            if (count.ContainsKey(num + 1)) {
                res = Math.Max(res, count[num] + count[num + 1]);
            }
            if (count.ContainsKey(num - 1)) {
                res = Math.Max(res, count[num] + count[num - 1]);
            }
        }
        
        return res;
    }
}

Ставь 👍 и забирай 📚 Базу знаний