二进制字符串中零和一的最大差值-C ++中的（O(n)time）

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

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

输入值

str = “10010110”

输出结果

2

说明

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

输入值

str = “00000”

输出结果

5

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

• 在main()函数中创建一个字符串str以存储二进制字符串。还声明一个数组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