最長ビトニック部分列の求め方：LISとLDSを組み合わせた動的計画法アルゴリズム

最長ビトニック部分列とは

「ビトニック列（bitonic sequence）」とは、最初は単調に増加し、その後単調に減少する性質を持つ数列のことです。本問題では、正の整数からなる配列が与えられ、その中から「まず増加し、次に減少する」部分列（ビトニック部分列）のうち最も長いものの長さを求めます。

この問題を解くためには、次の2つの配列を定義します。

• 最長増加部分列（LIS: Longest Increasing Subsequence）：各位置 i について、array[i] を終端とする増加部分列の最大長を記録します。
• 最長減少部分列（LDS: Longest Decreasing Subsequence）：各位置 i について、array[i] を始点とする減少部分列の最大長を記録します。

各位置 i を頂点とするビトニック部分列の長さは「incSubSeq[i] + decSubSeq[i] − 1」で求められます（頂点となる要素を2回数えないよう、1を引きます）。この最大値が最長ビトニック部分列の長さとなります。

入力と出力

入力：
数列 {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
出力：
最長ビトニック部分列の長さ。この例では 7。

アルゴリズム

longBitonicSub(array, size)

入力：配列とそのサイズ。

出力：最長ビトニック部分列の最大長。

Begin
    配列と同じサイズの incSubSeq を定義する
    incSubSeq の全要素を 1 で初期化する

    for i := 1 to size - 1, do
        for j := 0 to i - 1, do
            if array[i] > array[j] and incSubSeq[i] < incSubSeq[j] + 1,
                then incSubSeq[i] := incSubSeq[j] + 1
        done
    done

    配列と同じサイズの decSubSeq を定義する
    decSubSeq の全要素を 1 で初期化する

    for i := size - 2 down to 0, do
        for j := size - 1 down to i + 1, do
            if array[i] > array[j] and decSubSeq[i] < decSubSeq[j] + 1,
                then decSubSeq[i] := decSubSeq[j] + 1
        done
    done

    max := incSubSeq[0] + decSubSeq[0] - 1
    for i := 1 to size - 1, do
        if incSubSeq[i] + decSubSeq[i] - 1 > max,
            then max := incSubSeq[i] + decSubSeq[i] - 1
    done

    return max
End

アルゴリズムのポイント

LISは配列を左から右へ走査して計算し、LDSは右から左へ走査して計算します。これにより、各要素を頂点とするビトニック部分列の長さがすべて求まります。計算量は O(n²)、必要な追加メモリは O(n) です。

C++による実装例

#include<iostream>
using namespace std;

int longBitonicSub(int arr[], int size) {
    int *increasingSubSeq = new int[size];      // 増加部分列用の配列を作成
    for (int i = 0; i < size; i++)
        increasingSubSeq[i] = 1;                // すべての値を 1 に設定

    for (int i = 1; i < size; i++)              // 左から右へ計算
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
                increasingSubSeq[i] = increasingSubSeq[j] + 1;

    int *decreasingSubSeq = new int[size];      // 減少部分列用の配列を作成
    for (int i = 0; i < size; i++)
        decreasingSubSeq[i] = 1;                // すべての値を 1 に設定

    for (int i = size - 2; i >= 0; i--)         // 右から左へ計算
        for (int j = size - 1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
                decreasingSubSeq[i] = decreasingSubSeq[j] + 1;

    int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
    for (int i = 1; i < size; i++)              // 最大長を求める
        if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
            max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
    return max;
}

int main() {
    int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
    int n = 16;
    cout << "Length of longest bitonic subsequence is " << longBitonicSub(arr, n);
}

実行結果

Length of longest bitonic subsequence is 7

まとめ

最長ビトニック部分列の問題は、LISとLDSという2つの古典的な動的計画法の問題を組み合わせることで解決できます。各要素を「山の頂点」とみなし、左からの最長増加列と右からの最長減少列を足し合わせるという発想がポイントです。計算量 O(n²)・追加メモリ O(n) で動作し、実用的な規模の入力に対して十分高速に処理できます。