C++で最長ビトニック部分列の長さを求めるプログラム

数値のリストが与えられたとき、その中から「最長ビトニック部分列(バイトニックサブシーケンス)」の長さを求める問題を考えてみましょう。

ビトニック列とは、まず厳密に増加し、その後に厳密に減少するような数列のことです。なお、厳密に増加のみの数列や、厳密に減少のみの数列についても、ビトニック列として扱われます。

例えば、入力が nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15](要素数16)である場合、出力は 7 になります。

解法のアプローチ

この問題は動的計画法(DP)を用いて効率的に解くことができます。基本的な手順は以下の通りです。

• 各位置 i を終点とする最長増加部分列(LIS)の長さを記録する配列 increasingSubSeq を用意し、すべて 1 で初期化します。

• i を 1 から size-1 まで順に走査し、各 i に対して j(0 ≤ j < i)を調べます。arr[i] > arr[j] かつ increasingSubSeq[i] < increasingSubSeq[j] + 1 を満たす場合、increasingSubSeq[i] を increasingSubSeq[j] + 1 に更新します。

• 同様に、各位置 i を始点とする最長減少部分列(LDS)の長さを記録する配列 decreasingSubSeq を用意し、すべて 1 で初期化します。

• i を size-2 から 0 まで逆順に走査し、各 i に対して j(size-1 ≥ j > i)を調べます。arr[i] > arr[j] かつ decreasingSubSeq[i] < decreasingSubSeq[j] + 1 を満たす場合、decreasingSubSeq[i] を decreasingSubSeq[j] + 1 に更新します。

• 各位置 i における increasingSubSeq[i] + decreasingSubSeq[i] − 1 の最大値を求めます。ここで 1 を引くのは、山の頂点となる要素が増加側と減少側の両方で二重にカウントされるためです。

それでは、実際の実装を見て理解を深めましょう。

実装例

#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;
    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;
    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 << longBitonicSub(arr, n);
}

入力

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

出力

7

このアルゴリズムの計算量は O(n²)、必要なメモリは O(n) となります。LIS(最長増加部分列)と LDS(最長減少部分列)をそれぞれ前方向・後方向のDPで求め、両者を組み合わせることで、任意の位置を頂点とするビトニック部分列の最大長を正確に算出できるのがポイントです。