Longest Harmonious Subsequence ใน C++

แนวคิด

ได้รับอาร์เรย์จำนวนเต็ม ให้หาความยาวของ longest harmonious subsequence ในทุก subsequence ที่เป็นไปได้ Harmonious sequence คืออาร์เรย์ที่ผลต่างระหว่างค่าสูงสุดและต่ำสุดเท่ากับ 1 อย่างแน่นอน

เช่น ถ้าอินพุตคือ [1,3,2,2,5,2,3,7] ผลลัพธ์คือ 5 เพราะ longest harmonious subsequence คือ [4,3,3,3,4]

วิธีแก้:

• กำหนด map m
• สำหรับ n ใน nums: เพิ่ม m[n] ขึ้น 1
• สำหรับคู่ key-value (k,v) ใน m:
  • it := ตำแหน่งของ (k+1) ใน m
  • ถ้า 'it' อยู่ใน m แล้ว: max_ := max ของ max_ และค่าของ it
• คืนค่า max_

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> m;
        for (const int n : nums)
            ++m[n];
        int max_{0};
        for (const auto & [k, v] : m) {
            auto it = m.find(k + 1);
            if (it != m.end())
                max_ = max(max_, v + it->second);
        }
        return max_;
    }
};
main() {
    Solution ob;
    vector<int> v = {2,4,3,3,6,3,4,8};
    cout << (ob.findLHS(v));
}

อินพุต

{2,4,3,3,6,3,4,8}

เอาต์พุต

5