C++で最長の等差部分列を求めるアルゴリズムを解説

問題の概要

整数の配列 A が与えられたとき、A に含まれる「最長の等差部分列」の長さを返すことを考えます。

まず用語を確認しましょう。配列 A の部分列とは、A[i_1], A[i_2], ..., A[i_k](0 <= i_1 < i_2 < ... < i_k <= A.length - 1)のように、元の配列から順序を保ったまま一部の要素を取り出してできる列のことです。また、数列 B が「等差数列」であるとは、隣接する要素の差 B[i+1] - B[i] がすべて同じ値になること(0 <= i < B.length - 1)を指します。

例として、入力が [9, 4, 7, 2, 10] の場合を考えてみます。このとき最長の等差部分列は [4, 7, 10](公差 3)なので、出力は 3 となります。

解法のアプローチ:動的計画法

この問題は、動的計画法(DP)を用いることで効率的に解くことができます。ポイントは、「各インデックス i と公差 diff の組み合わせごとに、その公差で i まで到達する最長部分列の長さを記録する」ことです。

具体的な手順は以下の通りです。

• マップ dp を用意し、n を A のサイズ、ret を 2(最小の答え)で初期化します。
• i を 0 から n - 1 まで繰り返します。
  • j を 0 から i - 1 まで繰り返します。
    • diff := A[j] - A[i] として公差を計算します。
    • dp[i, diff] := 1 + dp[j, diff] として、j で終わる同じ公差の部分列に A[i] をつなげます。
    • ret := max(1 + dp[i, diff], ret) として答えを更新します。
• 最後に ret を返します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestArithSeqLength(vector<int>& A) {
      unordered_map <int, unordered_map <int, int> > dp;
      int n = A.size();
      int ret = 2;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < i; j++){
            int diff = A[j] - A[i];
            dp[i][diff] = 1 + dp[j][diff];
            ret = max(1 + dp[i][diff], ret);
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {9,4,7,2,10};
   Solution ob;
   cout << (ob.longestArithSeqLength(v1));
}

入力

[9,4,7,2,10]

出力

3

計算量の評価

このアルゴリズムの時間計算量は O(n²) です。すべてのインデックスのペア (i, j) を調べる必要があるためです。空間計算量も、dp テーブルのサイズに比例して O(n²) となります。全ての部分列を列挙する素朴な方法が O(2ⁿ) かかることを考えると、大幅な高速化を実現できていることがわかります。