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

任意のサイズの整数型配列が与えられたとき、「隣接する要素間の差が0または1」という条件を満たす最大長の部分配列(サブ配列)を見つけることが本記事の課題です。

問題例

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

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

説明 − 差が0または1となる隣接要素の組は {2, 1}、{5, 6}、{3, 4}、{7, 6} の4つです。いずれも長さが2であるため、最大長の部分配列の長さは2となります。

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

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

説明 − 差が0または1となる隣接要素の組は {2, 1} と {7, 6, 5} です。このうち {7, 6, 5} が最も長いため、最大長の部分配列の長さは3となります。

プログラムで使用するアプローチ

• 正の要素と負の要素の両方を含みうる整数型の配列を入力として受け取ります。
• 配列のサイズを計算し、配列とサイズを関数に渡して以降の処理を行います。
• 一時変数 i を0に初期化し、最大長を格納する変数 maximum も0に初期化します。
• i が配列のサイズに達するまで while ループを実行します。
• ループの先頭で j を i に設定し、走査開始位置を記録します。
• 内側のループで、隣接する要素間の差が0または1であるかどうかを abs() 関数で判定しながら部分配列を伸ばしていきます。
• 条件を満たす限り i の値をインクリメントします。
• temp に現在の部分配列の長さ i - j + 1 を設定します。
• maximum が temp より小さい場合は、maximum を temp で更新します。
• j が i と等しい場合(隣接要素の条件を一度も満たさなかった場合)は、i をインクリメントして次の要素へ進みます。
• maximum を返します。
• 結果を出力します。

このアルゴリズムは配列を一度だけ走査するため、計算量は O(n)、追加のメモリ使用量は O(1) であり、非常に効率的です。

サンプルコード

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

出力結果

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