이진 문자열에서 0과 1의 최대 차이 - C++의 (O(n) 시간)

주어진 작업은 주어진 이진 문자열에서 하위 문자열을 찾은 다음 0과 1의 수 사이의 최대 차이를 찾는 것입니다.

이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -

입력

str = “10010110”

출력

2

설명

위치 1에서 4("0010")까지의 하위 배열에서 0과 1의 차이 =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