Chuỗi con hài hòa dài nhất trong C ++

Giả sử chúng ta có một mảng số nguyên; chúng ta phải tìm độ dài của dãy con hài hòa dài nhất của nó trong số tất cả các dãy con có thể có của nó. Như chúng ta đã biết, một mảng trình tự hài hòa là một mảng có hiệu số giữa giá trị lớn nhất và giá trị nhỏ nhất của nó chính xác là 1.

Vì vậy, nếu đầu vào giống như [1,3,2,2,5,2,3,7], thì đầu ra sẽ là 5, vì dãy con hài hòa dài nhất là [4,3,3,3,4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ m

• cho n trong nums -

  • (tăng m [n] lên 1)

• cho cặp khóa-giá trị (k, v) trong m -

  • it:=vị trí của (k + 1) tính bằng m

  • nếu 'nó' bằng m, thì -

    • max _:=tối đa của max_ và giá trị của nó

• trả về max_

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

5