ลำดับที่กลมกลืนกันยาวนานที่สุดใน C++

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

ดังนั้น หากอินพุตเป็น [1,3,2,2,5,2,3,7] ผลลัพธ์จะเป็น 5 เนื่องจากลำดับที่ต่อเนื่องกันที่ยาวที่สุดคือ [4,3,3,3,4]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดหนึ่งแผนที่ m
สำหรับ n เป็นจำนวน −
- (เพิ่ม m[n] ขึ้น 1)
สำหรับคู่คีย์-ค่า (k,v) ในหน่วย m -
- มัน :=ตำแหน่งของ (k+1) ในหน่วย m
- ถ้า 'มัน' เป็น m แล้ว −
  - max_:=สูงสุดของ 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}