ผลรวมบิตเซ็ตสูงสุดในอาร์เรย์โดยไม่พิจารณาสมาชิกติดกันใน C++

คำอธิบายปัญหา

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม งานของเราคือสร้างโปรแกรมเพื่อคำนวณผลรวมบิตเซ็ตสูงสุดในอาร์เรย์โดยไม่พิจารณาสมาชิกติดกันใน C++

คำอธิบายปัญหา - ที่นี่ เรามีอาร์เรย์ arr[] เราต้องหาจำนวนบิตเซ็ตสำหรับแต่ละตัวเลข จากนั้นเราจะหาผลรวมบิตเซ็ตสูงสุดในสมาชิกติดกันของอาร์เรย์ เช่น ผลรวมสูงสุดสำหรับ a[i] + a[i+2] ...

ตัวอย่าง

มาดูตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

arr[] = {1, 4, 6, 7}

เอาต์พุต

4

คำอธิบาย

อาร์เรย์พร้อมสมาชิกในรูปแบบไบนารี

arr[] = {01, 100, 101, 111} Bit count array = {1, 1, 2, 3}

บิตเซ็ตสลับกัน

arr[0] + arr[2] = 1 + 2 = 3
arr[1] + arr[3] = 1 + 3 = 4

Max sum = 4

วิธีแก้ปัญหา

เพื่อแก้ปัญหานี้ เราจะหาจำนวนบิตเซ็ตในตัวเลข และหาคู่สลับที่มีจำนวนบิตเซ็ตสูงสุด

ผลรวมสูงสุดจะเป็นของอาร์เรย์ที่เริ่มต้นที่ 0 หรือเริ่มต้นที่ 1 ดังนั้นเราแค่ต้องตรวจสอบทั้งสองกรณี

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

โปรแกรมแสดงการทำงานของคำตอบของเรา

#include<iostream> 
using namespace std; 

int countSetBit(int n){ 
    int setBits = 0; 
    while(n) { 
        setBits++; 
        n = 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]); 
        } 
    } 
    if(EvenSum >= OddSum){ 
        return EvenSum; 
    } 
    return 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; 
}

เอาต์พุต

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