C++에서 가장 긴 조화로운 부분수열

정수 배열이 있다고 가정합니다. 가능한 모든 부분 수열 중에서 가장 긴 조화 부분 수열의 길이를 찾아야 합니다. 우리가 알고 있듯이 조화 시퀀스 배열은 최대값과 최소값의 차이가 정확히 1인 배열입니다.

따라서 입력이 [1,3,2,2,5,2,3,7]과 같으면 가장 긴 조화 부분 수열이 [4,3,3,3,4]이므로 출력은 5가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 맵 정의
n의 경우 -
- (m[n]을 1씩 증가)
m −
의 키-값 쌍(k,v)에 대해
- it :=m에서 (k+1)의 위치
- 'it'이 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}