C ++でプログラムを作成して、合計がゼロの最大のサブ配列の長さを見つけます

最大長を持つサブ配列の長さを見つけることがタスクであるN個の整数の配列を与えたと仮定します。長さが最大または合計が0に等しいサブ配列がない場合は、「0」を返します。たとえば、

入力-1 −

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

出力 −

4

説明 −合計がゼロの最大のサブ配列は{-5、-1、5、1}で、長さは4です。

入力-2 −

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

出力 −

0

説明 −合計がゼロに等しいサブ配列が存在しないため、出力は「0」です。

この問題を解決するためのアプローチ

この特定の問題を解決するためのいくつかのアプローチがあります。線形時間O（n）で解くための最も適切なアルゴリズムは、ハッシュテーブルを使用することです。

アイデアは、合計がキーとして格納され、インデックスが値として格納されるすべてのサブ配列の合計を格納するハッシュテーブルを作成することです。

まず、配列全体をトラバースし、現在の合計を格納します。現在の合計がハッシュテーブルで利用可能かどうかを確認します。ハッシュテーブルに存在する場合は、サブアレイの最大長を更新します。

• 配列のNサイズを入力します。

• 関数lenMax（int * arr、int size）は、配列とそのサイズを入力として受け取り、合計ゼロを含むサブ配列の最大長を返します。

• 合計としてキーを含み、インデックスとして値を含む整数の順序付けられていないマップは、合計が繰り返されているかどうかをチェックします。

• 配列要素を反復処理し、合計がハッシュテーブルに存在する場合は配列の現在の合計を見つけてから、サブ配列の最大長を見つけます。そうでない場合は、新しい合計とそのインデックスを使用してハッシュテーブルに挿入します。

• 最大長を出力として返します。

例

#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

sum =0の最大のサブ配列は{-2、2、-8、1、7}です。したがって、最大のサブアレイの長さは「5」です。