C ++中二进制字符串中零和一的最大差

给定任务是从给定的二进制字符串中找到一个子字符串，然后找到零和一之间的最大差。

现在让我们使用示例了解我们必须做的事情-

输入值

str = “100100110”

输出结果

2

说明

在位置1到5（“ 00100”）的子数组中，零和一之间的差= 4 – 1 = 3，这是可以找到的最大值。

输入值

str = “00000”

输出结果

5

在以下程序中使用的方法如下

• 在main()函数中，创建一个字符串str来存储二进制字符串。还初始化一个变量int size以存储字符串的大小，并将它们都传递给Max()函数。

• 在Max()函数中，首先通过调用One()函数检查所有元素是否均为1。

• 创建类型为bool的One()函数，并在其中创建变量int O = 0。

• 从i = 0循环直到i <str.size()，如果str [i] == 1，则将1加到变量O。

• 在循环外部，检查是否（O == size）。如果是这样，则返回true。

• 如果One()函数返回true，则返回Max()函数，然后返回-1作为答案。

• 否则继续寻找长度。初始化一个数组int a [100] = {0}。

• 从i = 0循环直到i <size，然后放入a [i] =（str [i] =='0'？1：-1）并以此方式检查str的每个元素。

• 在循环外部，初始化另一个数组int arr [100] [3]，并使用memset（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