C++で隣接する要素間の差が0または1となる最長部分列を求める方法

任意のサイズの整数配列が与えられ、その中から「隣接する要素同士の差が0または1」という条件を満たす部分列(サブシーケンス)のうち、最も長いものを見つけるのが本記事のテーマです。

問題の例

入力 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }

出力 − 隣接する要素間の差が0または1となる部分列の最大長は: 3

説明 − 例えば {5, 6, 7} や {6, 7, 6} のように、隣接する要素間の差がすべて0または1となる部分列を選ぶことができます。これらの長さは3となり、これが最大長です。

入力 − int arr[] = { 2, 1, 7, 6, 5 }

出力 − 隣接する要素間の差が0または1となる部分列の最大長は: 3

説明 − 配列中の {7, 6, 5} は隣接要素間の差がすべて1であり、この部分列の長さ3が最大となります。

プログラムで使用しているアプローチ

• 正の要素と負の要素のどちらも含み得る整数型の配列を入力として受け取ります。
• 配列のサイズを計算し、後続の処理のために配列とサイズを関数へ渡します。
• 入力配列と同じサイズの一時配列 temp[size] を用意し、変数 maximum を宣言して0で初期化します。
• i を0から配列サイズまで回すループを開始します。
• ループ内で temp[i] に1を設定します(どの要素もそれ単体で長さ1の部分列となるため)。
• 次に、i を1からsizeまで回す外側のループを開始します。
• その内側で、j を0から i 未満まで回すネストされたループを開始します。
• ループ内で、arr[i] と arr[j] の差の絶対値が1以下(つまり差が0または1)かつ temp[i] < temp[j] + 1 である場合、temp[i] に temp[j] + 1 を代入します。
• 最後に、i を0からsizeまで回すループを実行します。
• ループ内で、maximum が temp[i] より小さければ maximum = temp[i] とします。
• maximum を返します。
• 結果を出力します。

動作の仕組み(動的計画法)

このアルゴリズムは、最長増加部分列(LIS)の問題とよく似た動的計画法の手法を用いています。temp[i] には「i番目の要素を末尾とする、条件を満たす部分列の最長の長さ」が格納されます。各位置 i に対してそれより前のすべての位置 j を調べ、arr[j] と arr[i] の差が0または1であれば、arr[j] で終わる部分列の末尾に arr[i] を追加できるため、temp[i] を temp[j] + 1 で更新します。二重ループを使用するため、時間計算量は O(n²) となります。

コード例

#include <bits/stdc++.h>
using namespace std;
//最長の部分列の長さを計算する関数
int maximum_adja(int arr[], int size){
   int temp[size], maximum = 0;
   for (int i=0; i<size; i++){
      temp[i] = 1;
   }
   for (int i=1; i<size; i++){
      for (int j=0; j<i; j++){
         if (abs(arr[i] - arr[j]) <= 1 && temp[i] < temp[j] + 1){
            temp[i] = temp[j] + 1;
         }
      }
   }
   for (int i=0; i<size; i++){
      if (maximum < temp[i]){
         maximum = temp[i];
      }
   }
   return maximum;
}
int main(){
   int arr[] = {1, 5, 3, 7, 8, 9, 2};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"隣接する要素間の差が0または1となる部分列の最大長: "<<maximum_adja(arr, size);
   return 0;
}

出力

隣接する要素間の差が0または1となる部分列の最大長: 3