Cho số n. Có thể đảo một bit để tạo dãy 1 dài nhất. n=13, nhị phân 1101. Đảo 0 thành 1 thành 1111, dãy 1 dài nhất.
Giải quyết: duyệt các bit. Theo dõi độ dài dãy 1 hiện tại (curr) và trước (prev). Gặp 0: cập nhật prev. Nếu bit tiếp theo 1, prev=curr. Nếu 0, prev=0.
Ví dụ mã nguồn
#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); } Kết quả
Maximum length of the sequence with 1s: 4