ภาพรวมปัญหา
หาจำนวน 1 หรือ 0 ที่ติดต่อกันมากที่สุดในอาร์เรย์แบบวน (Circular Array) ซึ่งถือว่าอิลิเมนต์ตัวแรกอยู่ติดกับตัวสุดท้าย
ตัวอย่าง
Input: Arr[] = {1,1,0,1,0,1,0,1,1,1}
Output: Max consecutive 1's = 5, Max consecutive 0's = 1
Explanation: 1's ตรง index 7-9 และ 0-1 รวม 5 ตัว
Input: Arr[] = {0,0,0,1,0}
Output: Max consecutive 1's = 1, Max consecutive 0's = 4
Explanation: 0's ตรง index 4 และ 0-3 รวม 4 ตัว
แนวทางแก้ปัญหา
- คัดลอกอาร์เรย์ 2 ครั้งติดกัน (ทำให้เป็น linear array ความยาว 2N)
- นับ consecutive bits ในอาร์เรย์ที่ขยายแล้ว
- จำกัดความยาวสูงสุดไม่เกิน N
ตัวอย่างโค้ด C++
#include <iostream>
int maxConsecutive(int arr[], int n, int bit) {
int temp[2*n] = {0};
int k = 0;
for (int j = 0; j < 2; j++)
for (int i = 0; i < n; i++)
temp[k++] = arr[i];
int maxC = 0;
for (int i = 0; i < 2*n; i++) {
int count = 0;
while (k < 2*n && temp[k++] == bit) count++;
maxC = max(maxC, count);
}
return min(maxC, n); // ไม่เกินขนาดอาร์เรย์เดิม
}
int main() {
int Arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1};
int N = 12;
cout << "Max 1's: " << maxConsecutive(Arr, N, 1) << endl;
cout << "Max 0's: " << maxConsecutive(Arr, N, 0);
return 0;
}
ผลลัพธ์
Maximum Consecutive 1's in circular array: 6 Maximum Consecutive 0's in circular array: 2
