Số 1 hoặc 0 liên tiếp tối đa trong mảng nhị phân vòng tròn C++

Cho mảng nhị phân Arr[] (chỉ chứa 0 và 1) được coi là vòng tròn (phần tử cuối nối với phần tử đầu). Tìm số lượng bit 1 liên tiếp tối đa và bit 0 liên tiếp tối đa.

Ví dụ

Arr = {1,1,0,1,0,1,0,1,1,1} → Max 1's = 5 (chỉ số 7,8,9,0,1), Max 0's = 1
Arr = {0,0,0,1,0} → Max 1's = 1, Max 0's = 4 (chỉ số 4,0,1,2,3)

Kỹ thuật mảng gấp đôi

Tạo mảng temp[2*N] = Arr nối tiếp Arr. Duyệt temp tìm chuỗi liên tiếp dài nhất của bit cần tìm, nhưng giới hạn độ dài ≤ N.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

int maxConsecutiveCircular(int arr[], int n, int bit) {
    vector temp(2 * n);
    for (int i = 0; i < 2 * n; i++) temp[i] = arr[i % n];
    
    int maxLen = 0, curLen = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (temp[i] == bit) {
            curLen++;
            maxLen = max(maxLen, min(curLen, n)); // Không vượt quá N
        } else {
            curLen = 0;
        }
    }
    return maxLen;
}

int main() {
    int arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1};
    int n = 12;
    cout << "Max 1's: " << maxConsecutiveCircular(arr, n, 1) << endl; // 6
    cout << "Max 0's: " << maxConsecutiveCircular(arr, n, 0) << endl; // 2
    return 0;
}

Kết quả

Max 1's: 6
Max 0's: 2

Độ phức tạp

O(N) thời gian, O(N) bộ nhớ thêm. Có thể tối ưu O(1) bộ nhớ bằng cách duyệt 2 vòng không cần mảng temp.