C++で合計が0となる最長部分配列の長さを求めるプログラムの作成方法

N個の整数からなる配列が与えられ、「合計が0となる最長の部分配列の長さ」を見つけることが課題です。もし合計が0となる部分配列が存在しない場合は「0」を返します。それでは、具体例を見てみましょう。

入力例1：

N = 8
A[ ] = {15, -5, -1, 5, 1, 4 }

出力：

4

説明： 合計が0となる最長の部分配列は { -5, -1, 5, 1 } であり、その長さは4です。

入力例2：

N = 5
A[ ] = {3, 2, 4, 8, -1}

出力：

0

説明： 合計が0となる部分配列がひとつも存在しないため、出力は「0」になります。

この問題の解き方

この問題を解くには複数のアプローチがありますが、線形時間 O(n) で解くのに最も適したアルゴリズムが「ハッシュテーブル」を使う方法です。

基本的な考え方は、これまでに現れた部分配列の合計をキーとして、その合計が最初に現れたインデックスを値としてハッシュテーブルに保存しておくことです。配列を先頭から走査しながら現在までの累積和を計算し、その合計がすでにハッシュテーブルに登録済みであれば、同じ合計が再び現れたということは、間の要素の合計が0であることを意味します。このとき、部分配列の最大長を更新します。

アルゴリズムの手順

• サイズNの配列を入力として受け取ります。
• 関数 lenMax(int *arr, int size) は、配列とそのサイズを引数に取り、合計が0となる部分配列の最大長を返します。
• 合計をキー、インデックスを値とする unordered_map を用意し、同じ合計が繰り返し現れていないかを判定します。
• 配列の各要素を走査して現在の累積和を求めます。その合計がハッシュテーブルに存在すれば、インデックスの差から部分配列の最大長を計算して更新します。存在しない場合は、新しい合計とそのインデックスをハッシュテーブルに挿入します。
• 最後に最大長を結果として返します。

実装例（C++コード）

#include<bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size){
    unordered_map<int,int>mp;
    int sum=0;
    int maxlen=0;
    for(int i=0;i<size;i++){
        sum+=arr[i];
        if(arr[i]==0 && maxlen==0){
            maxlen=1;
        }
        if(sum==0){
            maxlen=i+1;
        }
        if(mp.find(sum)!= mp.end()){
            maxlen= max(maxlen, i-mp[sum]);
        } else {
            mp[sum]=i;
        }
    }
    return maxlen;
}
int main(){
    int N=6;
    int A[N]={15,-2,2,-8,1,7,10,23};
    cout<<lenMax(A,N)<<endl;
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

5

この場合、合計が0となる最長の部分配列は { -2, 2, -8, 1, 7 } です。したがって、最長部分配列の長さは「5」となります。

このようにハッシュテーブルを活用することで、全ての部分配列を総当たりで調べるO(n²)やO(n³)の非効率な方法よりもはるかに高速に、線形時間O(n)で問題を解くことができます。