C++のバイナリ文字列の0と1の最大差

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

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

入力

str = “100100110”

出力

2

説明

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

入力

str = “00000”

出力

5

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

• main（）関数で、文字列 strを作成します バイナリ文字列を格納します。また、変数intサイズを初期化して、サイズを格納します。 文字列を取得し、両方をMax（）関数に渡します。

• Max（）関数では、最初にOne（）関数を呼び出して、すべての要素が1であるかどうかを確認します。

• bool型のOne（）関数を作成し、その中に変数int O=0を作成します。

• i =0からi

• ループの外側で、（O ==サイズ）かどうかを確認します。その場合は、trueを返します。

• One（）関数がtrueを返した場合は、Max（）関数に戻り、答えとして-1を返します。

• それ以外の場合は、長さを見つけます。配列を初期化しますinta[100]={0}。

• i =0からi

• ループの外側で、別の配列int arr [100] [3]を初期化し、me​​mset（arr、-1、sizeof arr）を使用してそのすべての要素を-1に置き換え、最後にLength（a、str、size、0、0、arr）を呼び出します。

• Length（）関数で、最初に（i> =size）かどうかを確認し、そうであれば、文字列が終了して0を返すことを意味します。

• 次に、（arr [i] [s]！=-1）かどうかを確認します。もしそうなら、それは状態がすでに計算されていることを意味し、arr[i][s]を返します。

• 次に、（s ==0）かどうかを確認します。その場合は、arr [i] [s] =max（a [i] + Length（a、str、size、i + 1、1、arr）、Length（a、str、size、i + 1、0）を返します。 、arr））;

• それ以外の場合は、arr [i] [s] =max（a [i] + Length（a、str、size、i + 1、1、arr）、0）;

  を返します。

例

#include <bits/stdc++.h>
using namespace std;
bool One(string str, int size){
   int O = 0;
   for (int i = 0; i < str.size(); i++)
      O += (str[i] == '1');
   return (O == size);
}
int Length(int a[], string str, int size,
int i, int s, int arr[][3]){
   // If string is over.
   if (i >= size)
      return 0;
      // If the already calculated.
   if (arr[i][s] != -1)
      return arr[i][s];
   if (s == 0)
      return arr[i][s] = max(a[i] +
      Length(a, str, size, i + 1, 1, arr),
      Length(a, str, size, i + 1, 0, arr));
   else
      return arr[i][s] = max(a[i] +
      Length(a, str, size, i + 1, 1, arr), 0);
}
int Max(string str, int size){
   // Checking if all elements are 1
   if (One(str, size))
      return -1;
      // Finding length
   int a[100] = { 0 };
   for (int i = 0; i < size; i++)
      a[i] = (str[i] == '0' ? 1 : -1);
      int arr[100][3];
      memset(arr, -1, sizeof arr);
   return Length(a, str, size, 0, 0, arr);
}
// main function
int main(){
   string str = "100100110";
   int size = 9;
   cout << Max(str, size);
   return 0;
}

出力

3