二进制字符串中零和一的最大差值-C ++中的(O(n)time)
给定任务是从给定的二进制字符串中找到一个子字符串,然后找到零和一之间的最大差。
现在让我们使用示例了解我们必须做的事情-
输入值
str = “10010110”
输出结果
2
说明
在从位置1到4(“0010”)的子数组中,零和一之间的差=3-1=2,这是可以找到的最大值。
输入值
str = “00000”
输出结果
5
在以下程序中使用的方法如下
在main()
函数中创建一个字符串str以存储二进制字符串。还声明一个数组intarr[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