C++의 이진 문자열에서 0과 1의 최대 차이

<시간/>

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

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

입력

str = “100100110”

출력

설명

위치 1에서 5까지의 하위 배열("00100")에서 0과 1의 차이 =4 – 1 =3이며 찾을 수 있는 최대값입니다.

입력

str = “00000”

출력

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

main() 함수에서 str 문자열을 만듭니다. 바이너리 문자열을 저장합니다. 또한 크기 를 저장하기 위해 가변 int 크기를 초기화합니다. 문자열로 만들고 둘 다 Max() 함수에 전달합니다.
Max() 함수에서 먼저 One() 함수를 호출하여 모든 요소가 1인지 확인합니다.
bool 유형의 One() 함수를 만들고 그 안에 int O =0 변수를 만듭니다.
i =0에서 i
루프 외부에서 if(O ==size)를 확인합니다. 그렇다면 true를 반환하십시오.
One() 함수가 true를 반환하면 Max() 함수로 돌아가서 답으로 -1을 반환합니다.
그렇지 않으면 계속해서 길이를 찾습니다. 배열 int a[100] ={ 0 }를 초기화합니다.
i =0에서 i
루프 외부에서 다른 배열 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]를 반환합니다.
그런 다음 if(s ==0)인지 확인하십시오. 그렇다면 arr[i][s] =max(a[i] + Length(a, str, size, i +1, 1, arr), Length(a, str, size, i + 1, 0)를 반환합니다. , arr));
그렇지 않으면 return 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;
}