Tổng bit 1 lớn nhất mảng không lấy phần tử liền kề trong C++

Mô tả bài toán

Cho mảng arr[]. Tìm tổng số bit 1 lớn nhất của dãy con lấy cách nhau (không lấy 2 phần tử liền kề). Tức là chọn các chỉ số chẵn hoặc lẻ.

Ví dụ: arr = {1, 4, 6, 7} → Nhị phân: {01, 100, 110, 111} → Bit count: {1, 1, 2, 3}. Chẵn: 1+2=3, Lẻ: 1+3=4 → Max = 4.

Giải pháp (Tính tổng chẵn/lẻ riêng)

• Đếm bit 1 cho mỗi số (dùng n & (n-1)).
• Tính EvenSum (chỉ số chẵn) và OddSum (chỉ số lẻ).
• Trả về max của hai tổng.

Ví dụ minh họa

#include <iostream>
using namespace std;

int countSetBit(int n) {
    int setBits = 0;
    while (n) { setBits++; n &= (n - 1); }
    return setBits;
}

int findMaxBitAltSubArray(int arr[], int n) {
    int EvenSum = countSetBit(arr[0]);
    int OddSum = 0;
    for (int i = 1; i < n; i++) {
        if (i % 2 == 0) EvenSum += countSetBit(arr[i]);
        else OddSum += countSetBit(arr[i]);
    }
    return max(EvenSum, OddSum);
}

int main() {
    int arr[] = {1, 4, 6, 7};
    int n = 4;
    cout << "The maximum set bit sum in the array without considering adjacent elements is " << findMaxBitAltSubArray(arr, n);
    return 0;
}

Đầu ra

The maximum set bit sum in the array without considering adjacent elements is 4