C++で整数配列の最長調和部分列（Longest Harmonious Subsequence）を求める方法

問題概要

整数型の配列が与えられたとき、そのすべての部分列の中から「調和的な部分列」のうち最も長いものの長さを求めます。ここでいう調和的な配列とは、最大値と最小値の差がちょうど1である配列のことです。

たとえば、入力が [1,3,2,2,5,2,3,7] の場合、答えは 5 になります。これは、3つの「2」と2つの「3」からなる部分列 [3,2,2,2,3] が最長の調和的部分列となるためです。

解法のアプローチ

この問題は、ハッシュマップを使って各値の出現回数を数えることで効率的に解けます。手順は以下の通りです。

• 出現回数を記録するためのマップ m を用意します。
• 配列 nums の各要素 n について、m[n] のカウントを1ずつ増やします。
• マップ m 内のすべてのキーと値のペア (k, v) について、次の処理を行います。
  • m 内にキー (k+1) が存在するかどうかを調べます。
  • 存在する場合は、現在の max_ と (v + m[k+1]) を比較し、大きい方で max_ を更新します。
• 最後に max_ を返します。

ポイントは、調和的な部分列を構成できるのは「値が k である要素」と「値が k+1 である要素」だけだという点です。したがって、隣接する2つの値の出現回数の合計をすべてのペアについて調べれば、答えが得られます。

C++での実装例

理解を深めるために、実際のC++コードを見てみましょう。なお、構造化束縛（structured bindings）を使用しているため、C++17以降のコンパイラが必要です。

#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

この入力の場合、「3」が3個、「4」が2個含まれているため、[3,3,3,4,4] という長さ5の調和的部分列を構成できます。これが最長となります。

計算量

• 時間計算量： O(n) — 配列を一度走査してマップを構築し、その後マップ内の各キーに対して定数時間の検索を行うだけです。
• 空間計算量： O(n) — 各要素の出現回数を格納するハッシュマップに、要素数に比例したメモリが必要です。