Longest Harmonious Subsequence trong C++

Cho một mảng số nguyên, ta cần tìm độ dài của dãy con hài hòa (harmonious subsequence) dài nhất. Dãy hài hòa là dãy mà hiệu giữa giá trị lớn nhất và nhỏ nhất đúng bằng 1.

Ví dụ: với mảng [1,3,2,2,5,2,3,7], dãy con hài hòa dài nhất là [3,2,2,2,3] (hoặc [2,3,3,3,2]) có độ dài 5.

Giải thuật

1. Dùng unordered_map freq để đếm tần suất xuất hiện của từng số.
2. Duyệt qua từng cặp (key, value) trong map:
   • Kiểm tra xem key + 1 có tồn tại trong map không.
   • Nếu có, cập nhật kết quả tối đa: maxLen = max(maxLen, value + freq[key+1]).
3. Trả về maxLen.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int n : nums) ++freq[n];
        
        int maxLen = 0;
        for (const auto& [k, v] : freq) {
            auto it = freq.find(k + 1);
            if (it != freq.end())
                maxLen = max(maxLen, v + it->second);
        }
        return maxLen;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,4,3,3,6,3,4,8};
    cout << ob.findLHS(v); // Kết quả: 5
    return 0;
}

Đầu vào / Đầu ra

Input: {2,4,3,3,6,3,4,8}
Output: 5