Chênh lệch tối đa của số không và số không trong chuỗi nhị phân - (O (n) thời gian) trong C ++

Nhiệm vụ được giao là tìm một chuỗi con từ một chuỗi nhị phân nhất định và sau đó là sự khác biệt lớn nhất giữa số lượng 0 và số một.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào

str = “10010110”

Đầu ra

2

Giải thích

Trong mảng con từ vị trí 1 đến 4 (“0010”), sự khác biệt giữa các số không và những người =3 - 1 =2 là giá trị lớn nhất có thể được tìm thấy.

Đầu vào

str = “00000”

Đầu ra

5

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Trong hàm main (), hãy tạo một chuỗi str để lưu trữ chuỗi nhị phân. Cũng khai báo anarray int arr [str.length () + 1];

• Đặt tất cả các phần tử của arr [] =0 bằng cách sử dụng memset (arr, 0, sizeof (arr));

• Vòng lặp từ j =1 đến j <=str.length ()

• Kiểm tra if (memset (arr, 0, sizeof (arr)), nếu vậy thì đặt arr [j] =max (arr [j-1] -1, -1);

• Khác đặt arr [j] =max (arr [j-1] +1,1);

• Bên ngoài vòng lặp, in số tối đa bằng cách sử dụng * max_element (arr + 1, arr + str.length () + 1);

Ví dụ

#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;
}

Đầu ra

2