C++で配列内の最大連続数を求める方法を解説

正の整数からなる配列が与えられたとき、その中に存在する「連続した整数」(値が1ずつ増えていく並び)の最大個数を求めることを考えます。

基本的な考え方は次のとおりです。まず配列を昇順にソートし、隣接する要素同士を比較します。arr[j]==arr[i]+1(j=i+1)が成り立てば連続していると判断できるため、カウントを1増やしてインデックスを進めます(i++、j++)。差が1でなければcountを1にリセットします。そして、それまでに見つかった最大のカウントをmaxcに記録していきます。

入力例1

Arr[]= { 100,21,24,73,22,23 }

出力例1

Maximum consecutive numbers in array : 4

解説: ソート後の配列は { 21,22,23,24,73,100 } となります。初期値は count=1、maxcount=1 です。

1. 22=21+1 → count=2, maxcount=2, i++, j++
2. 23=22+1 → count=3, maxcount=3, i++, j++
3. 24=23+1 → count=4, maxcount=4, i++, j++
4. 73≠24+1 → count=1, maxcount=4, i++, j++
5. 100≠73+1 → count=1, maxcount=4, i++, j++

したがって、最大連続数は4({ 21,22,23,24 })です。

入力例2

Arr[]= { 11,41,21,42,61,43,9,44 }

出力例2

Maximum consecutive numbers in array : 4

解説: ソート後の配列は { 9,11,21,41,42,43,44,61 } となります。初期値は count=1、maxcount=1 です。

1. 11≠9+1 → count=1, maxcount=1, i++, j++
2. 21≠11+1 → count=1, maxcount=1, i++, j++
3. 41≠21+1 → count=1, maxcount=1, i++, j++
4. 42=41+1 → count=2, maxcount=2, i++, j++
5. 43=42+1 → count=3, maxcount=3, i++, j++
6. 44=43+1 → count=4, maxcount=4, i++, j++
7. 61≠44+1 → count=1, maxcount=4, i++, j++

したがって、最大連続数は4({ 41,42,43,44 })です。

プログラムのアプローチ

• 整数型配列 Arr[] に整数を格納します。

• 整数 n には配列の長さを格納します。

• 関数 subs(int arr[], int n) は、配列とそのサイズを引数として受け取り、配列内に存在する最大連続数を返します。

• まず sort(arr,arr+n) を使って配列をソートします。

• 次に count=1、maxc=1 として初期化します。

• 最初の2要素 arr[0] と arr[1] から始めて、二重のforループ内で arr[j]==arr[i]+1(j=i+1)が成り立つかを比較し、真であれば count と i を1ずつ増やします。

• 上記の条件が偽の場合は count を1に戻します。maxc は常に見つかった最大のカウントで更新します(maxc = count > maxc ? count : maxc)。

• 最後に maxc を最大連続要素数として結果として返します。

サンプルコード

#include <iostream>
#include <algorithm>
using namespace std;
int subs(int arr[],int n){
    std::sort(arr,arr+n);
    int count=1;
    int maxc=1;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(arr[j]==arr[i]+1){
                count++;
                i++;
            }
            else
                count=1;
            maxc=count>maxc?count:maxc;
        }
    }
    return maxc;
}
int main(){
    int arr[] = { 10,9,8,7,3,2,1,4,5,6 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Maximum consecutive numbers present in an array :"<<subs(arr, n);
    return 0;
}

出力

Maximum consecutive numbers present in an array : 10

この例では、配列をソートすると { 1,2,3,4,5,6,7,8,9,10 } となり、すべての要素が連続しているため、最大連続数は10となります。