ペアの最大長チェーンを求めるアルゴリズム（動的計画法）

問題の概要

整数のペアからなる列が与えられます。各ペアは2つの整数を持ち、必ず最初の整数の方が2番目の整数より小さいというルールがあります。チェーンの構築にも同じルールが適用され、ペア (p, q) の後にペア (x, y) を追加できるのは、q < x が成り立つ場合のみです。

この問題を解くには、まず与えられたペアを最初の要素（a）の昇順にソートします。その後、各ペアの2番目の要素（b）と、それ以降のペアの1番目の要素（a）を比較しながら、動的計画法（DP）によって最長のチェーンの長さを求めます。

入力と出力

入力:
数値ペアのチェーン {(5, 24), (15, 25), (27, 40), (50, 60)}

出力:
条件を満たすチェーンの最大長。この例では 3。

アルゴリズム

maxChainLength(arr, n)

チェーンの各要素は a と b という2つの値を持ちます。

入力 − ペアの配列、および配列内の要素数 n

出力 − 最大チェーン長

Begin
   サイズ n の maxChainLen 配列を定義し、すべて 1 で初期化する
   max := 0

   for i := 1 to n, do
      for j := 0 to i-1, do
         if arr[i].a > arr[j].b かつ maxChainLen[i] < maxChainLen[j] + 1
            maxChainLen[i] := maxChainLen[j] + 1
      done
   done

   max := maxChainLen 配列内の最大値
   return max
End

仕組みの解説

maxChainLen[i] は「ペア i を終端とするチェーンの最大長」を表します。初期値はすべて 1（自分自身だけのチェーン）です。i 番目のペアに対して、それ以前のすべてのペア j を調べ、arr[j].b < arr[i].a（つまりペア j の後ろにペア i を接続できる）が成り立ち、かつ現在の値より maxChainLen[j] + 1 が大きい場合に値を更新します。最終的に配列全体の最大値が答えとなります。

計算量は、ソートに O(n log n)、DP部分に O(n²) が必要です。

C++による実装例

#include<iostream>
#include<algorithm>
using namespace std;

struct numPair {    // ペアを構造体として定義
   int a;
   int b;
};

int maxChainLength(numPair arr[], int n) {
   int max = 0;
   int *maxChainLen = new int[n];    // サイズ n の配列を作成

   for (int i = 0; i < n; i++ )    // すべてのインデックスのチェーン長を 1 で初期化
      maxChainLen[i] = 1;

   for (int i = 1; i < n; i++ )
      for (int j = 0; j < i; j++ )
         if ( arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)

            maxChainLen[i] = maxChainLen[j] + 1;

   // この時点で maxChainLen[i] は「ペア i で終わる最大チェーン長」を保持している

   for (int i = 0; i < n; i++ )
      if ( max < maxChainLen[i] )
         max = maxChainLen[i];    // すべてのチェーン長の中から最大値を求める
   delete[] maxChainLen;   // メモリを解放
   return max;
}

int main() {
   struct numPair arr[] = {{5, 24},{15, 25},{27, 40},{50, 60}};
   int n = 4;
   cout << "Length of maximum size chain is " << maxChainLength(arr, n);
}

出力結果

Length of maximum size chain is 3

この例では、(5, 24) → (27, 40) → (50, 60) という3つのペアをつなげることで、条件を満たす最長のチェーンが得られます。