C++で循環配列内の連続する1（または0）の最大数を求める方法

本記事では、循環配列（サーキュラー配列）を扱います。循環配列とは、最初の要素が最後の要素の直後に続くものとみなす配列のことで、キューの実装などによく利用されます。ここでは、このような配列の中で連続して現れる「1」または「0」の最大個数を数える方法を解説します。

具体的な例で確認してみましょう。

入力 − Arr[] = { 1,1,0,1,0,1,0,1,1,1 }

出力 − 連続する「1」の最大数は5。連続する「0」の最大数は1。

説明 − 配列のインデックス7から9、さらにインデックス0と1にまたがって「1」が5個連続しています。一方、「0」は連続して現れず、最大でも1個です。

入力 − Arr[] = { 0,0,0,1,0 }

出力 − 連続する「1」の最大数は1。連続する「0」の最大数は4。

説明 − インデックス4の「0」と、インデックス0から3までの「0」がつながり、合計4個連続しています。

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

• 「0」と「1」がランダムな順序で格納された配列Arr[]を入力として受け取ります。

• 変数Nは、配列Arr[]のサイズを表します。

• 変数bitには、カウント対象とする「1」または「0」を格納します。

• 関数maxConsecutive(int arr[], int n, int bit)は、配列そのもの・サイズ・bit（0または1）の3つの引数を受け取り、連続するbitの最大個数を返します。

• 配列を循環させて扱うために、Temp[2*n]という配列を用意し、arr[]の内容を2回コピーします。while()ループを2回回すことで、arr[]をtempへ複製しています。

• その後、while ( temp[k++]==bit ) を用いて連続する「1」（または「0」）を数え、その個数を変数countに保存します。

• このcountがそれまでに見つかった最大値を上回る場合、maxCに保存します。

• 最終的な結果としてmaxCを返します。

コード例

#include <iostream>
// 最大連続数を返す関数
int maxConsecutive(int arr[],int n,int bit){
    int count=0;
    int temp[2*n]={0};
    int maxC=0;
    int j=0,k=0; // arr[]を2回コピーするため
    while(j<2){
        for(int i=0;i<n;i++){
            temp[k++]=arr[i];
        }
        j++;
    }
    k=0;
    for(int i=0;i<2*n; i++){
        count=0;
        while(temp[k++]==bit){
            ++count;
        }
        if(maxC<count)
            maxC=count;
    }
    return maxC;
}
int main(){
    int Arr[]={1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 };
    int N = 12;
    int bit=1;
    printf("Maximum Consecutive 1's in circular array: %d",maxConsecutive(Arr,N,bit));
    bit=0;
    printf("\nMaximum Consecutive 0's in circular array: %d",maxConsecutive(Arr,N,bit));
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます −

Maximum Consecutive 1's in circular array: 6
Maximum Consecutive 0's in circular array: 2