โปรแกรม C++ หาลำดับ 1 ติดต่อกันยาวสุดในรูปแบบไบนารีด้วยการพลิกบิตเดียว

สมมติว่าเรามีจำนวนเต็ม n หนึ่งจำนวน ภายในนั้น เราสามารถทำการพลิกบิตหนึ่งบิตเพื่อสร้างลำดับ 1 ติดต่อกันที่ยาวที่สุด สมมติตัวเลขคือ 13 รูปแบบไบนารีคือ 1101 หากเราทำการพลิกบิตหนึ่งบิต คือ เปลี่ยน 0 เป็น 1 จะกลายเป็น 1111 นี่คือลำดับ 1 ติดต่อกันที่ยาวที่สุด

เพื่อแก้ปัญหานี้ เราจะเดินทางผ่านบิตของตัวเลขที่กำหนด เราจะติดตามความยาวลำดับ 1 ปัจจุบัน และความยาวลำดับ 1 ก่อนหน้า เมื่อพบศูนย์ ให้อัปเดตความยาวก่อนหน้า ดังนั้นถ้าบิตถัดไปคือ 1 ความยาวก่อนหน้าควรตั้งให้เท่ากับความยาวปัจจุบัน หากถัดไปคือ 0 ให้ทำให้ก่อนหน้าเป็น 0 อีกครั้ง

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

int singleFlipMaxOnes(unsigned number) {
    if (~number == 0)
        return 8*sizeof(int);
    int curr = 0, prev = 0, max_size = 0;
    while (number != 0) {
        if ((number & 1) == 1)
            curr++;
        else if ((number & 1) == 0) {
            prev = (number & 2) == 0? 0 : curr;
            curr = 0;
        }
        max_size = max(prev + curr, max_size);
        number >>= 1;
    }
    return max_size+1;
}

int main() {
    cout << "Maximum length of the sequence with 1s: " << singleFlipMaxOnes(13);
}

ผลลัพธ์

Maximum length of the sequence with 1s: 4