バイナリ文字列の0と1の最大差-C++では（O（n）時間）

与えられたタスクは、与えられたバイナリ文字列からサブ文字列を見つけ、次にゼロと1の数の最大差を見つけることです。

例を使用して、私たちがしなければならないことを理解しましょう-

入力

str = “10010110”

出力

2

説明

位置1から4（ "0010"）までのサブ配列では、ゼロと1の差=3 – 1 =2であり、これは検出可能な最大値です。

入力

str = “00000”

出力

5

以下のプログラムで使用されるアプローチは次のとおりです

• main（）関数で、文字列 strを作成します バイナリ文字列を格納します。また、anarray int arrを宣言します [str.length（）+ 1];

• memset（arr、0、sizeof（arr））;

  を使用して、arr []=0のすべての要素を設定します。

• j=1からj<=str.length（）

  までループします

• if（memset（arr、0、sizeof（arr））、そうであれば、arr [j] =max（arr [j-1] -1、-1）;

  を入力します。

• それ以外の場合は、arr [j] =max（arr [j-1] + 1,1）;

• ループの外側では、* max_element（arr + 1、arr + str.length（）+ 1）;

  を使用して最大数を出力します。

例

#include<bits/stdc++.h>
using namespace std;
int main(){
   string str = "10010110";
   int arr[str.length()+1];
   memset(arr,0,sizeof(arr));
   for(int j=1;j<=str.length();j++){
      if(str[j-1]=='1')
         arr[j]=max(arr[j-1]-1,-1);
      else
         arr[j]=max(arr[j-1]+1,1);
   }
   cout<<*max_element(arr+1,arr+str.length()+1);
   return 0;
}

出力

2