二进制字符串中零和一的最大差值-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