Tìm Chỉ số của 0 được thay thế bằng 1 để có chuỗi 1s liên tục dài nhất trong một mảng nhị phân trong C ++

Giả sử, chúng ta có một mảng gồm N phần tử. Các phần tử này là 0 hoặc 1. Tìm vị trí của 0 được thay bằng 1 để có dãy liền kề dài nhất là 1s. Giả sử mảng giống như arr =[1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1], chỉ số đầu ra là 9. Thay 0 bằng 1 ở chỉ số 9 gây ra trình tự liền kề tối đa là 1 giây

Chúng tôi phải theo dõi ba chỉ mục. chỉ số hiện tại (curr), chỉ số 0 trước đó (pz) và chỉ số 0 trước đó (ppz). Bây giờ duyệt qua mảng khi phần tử mảng là 0, sau đó tính toán chênh lệch giữa curr và ppz, Nếu chênh lệch lớn hơn max, thì cập nhật chỉ mục tối đa, cuối cùng trả về chỉ số của pres_zero với chênh lệch tối đa.

Ví dụ

#include<iostream>
using namespace std;
int findIndex(bool arr[], int n) {
   int count_max = 0;
   int index;
   int pz = -1;
   int ppz = -1;
   for (int curr=0; curr<n; curr++) {
      if (arr[curr] == 0) {
         if (curr - ppz > count_max){
            count_max = curr - ppz;
            index = pz;
         }
         ppz = pz;
         pz = curr;
      }
   }
   if (n-ppz > count_max)
      index = pz;
   return index;
}
int main() {
   bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Index of 0 to be replaced is "<< findIndex(arr, n);
}

Đầu ra

Index of 0 to be replaced is 9