Sự khác biệt tối đa của số không và số không trong chuỗi nhị phân 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 = “100100110”

Đầu ra

Giải thích

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

Đầu vào

str = “00000”

Đầu ra

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. Đồng thời khởi tạo kích thước int sẵn có để lưu trữ kích thước của chuỗi và chuyển cả hai vào hàm Max ().
Trong hàm Max (), trước tiên hãy kiểm tra xem tất cả các phần tử có phải là 1 hay không bằng cách gọi hàm One ().
Tạo hàm One () kiểu bool và bên trong nó tạo một biến int O =0.
Lặp lại từ i =0 đến i
Bên ngoài vòng lặp, hãy kiểm tra xem (O ==size). Nếu vậy, hãy trả về true.
Quay lại hàm Max () nếu sau đó hàm One () trả về true, hãy trả về -1 dưới dạng theanswer.
Khác tiến hành để tìm độ dài. Khởi tạo mảng int a [100] ={0}.
Lặp lại từ i =0 cho đến khi i
Bên ngoài vòng lặp, khởi tạo một mảng khác int arr [100] [3] và thay thế tất cả các phần tử của nó bằng -1 bằng cách sử dụng memset (arr, -1, sizeof arr) và cuối cùng gọi Length (a, str, size, 0, 0, arr)
Trong hàm Length (), trước tiên hãy kiểm tra xem (i> =size), nếu có, thì nó có nghĩa là chuỗi đang ở mức trung bình và trả về bằng 0.
Sau đó kiểm tra xem (arr [i] [s]! =-1). Nếu vậy, điều đó có nghĩa là trạng thái đã được tính toán nhanh và trả về arr [i] [s].
Sau đó, kiểm tra xem (s ==0). Nếu vậy, thì trả về arr [i] [s] =max (a [i] + Length (a, str, size, i +1, 1, arr), Length (a, str, size, i + 1, 0 , arr));
Trả về khác arr [i] [s] =max (a [i] + Length (a, str, size, i + 1, 1, arr), 0);

Ví dụ

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