Tìm chỉ số 0 cần đổi thành 1 để có dãy 1 liên tiếp dài nhất trong mảng nhị phân C++

Cho mảng nhị phân (chỉ chứa 0 và 1). Tìm chỉ số của phần tử 0 mà nếu đổi thành 1 sẽ cho dãy 1 liên tiếp dài nhất. Ví dụ: [1,1,0,0,1,0,1,1,1,0,1,1,1] → chỉ số 9.

Ý tưởng: Theo dõi 3 chỉ số: current (curr), previous zero (pz), previous-previous zero (ppz). Khi gặp 0, tính curr - ppz, nếu lớn hơn max thì cập nhật max và lưu pz. Cuối mảng kiểm tra lần cuối.

Ví dụ

#include <iostream>
using namespace std;

int findIndex(bool arr[], int n) {
    int count_max = 0, index = -1;
    int pz = -1, 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);
}

Kết quả

Index of 0 to be replaced is 9