C++의 이진 배열에서 1의 가장 긴 연속 시퀀스를 얻기 위해 1로 바꿀 0의 인덱스 찾기

N개의 요소로 구성된 배열이 있다고 가정합니다. 이 요소는 0 또는 1입니다. 1의 가장 긴 연속 시퀀스를 얻기 위해 1로 대체될 0의 위치를 ​​찾습니다. 배열이 arr =[1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]과 같다고 가정하고 출력 인덱스는 9입니다. 인덱스 9에서 0을 1로 바꾸면 1의 최대 연속 시퀀스

3개의 인덱스를 추적해야 합니다. 현재 인덱스(curr), 이전 제로 인덱스(pz), 이전 제로 인덱스(ppz). 이제 배열 요소가 0일 때 배열을 탐색한 다음 curr과 ppz 사이의 차이를 계산합니다. 차이가 최대값보다 크면 최대값을 업데이트하고 마지막으로 최대 차이가 있는 prev_zero의 인덱스를 반환합니다.

예시

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

출력

Index of 0 to be replaced is 9