Tổng OR lớn nhất của các mảng con từ hai mảng khác nhau trong C++

Đề bài

Cho hai mảng số nguyên dương. Chọn hai mảng con cùng kích thước từ mỗi mảng và tính tổng OR lớn nhất có thể của hai mảng con đó.

Ví dụ

Nếu arr1[] = {1, 2, 4, 3, 2} và arr2[] = {1, 3, 3, 12, 2} thì kết quả lớn nhất đạt được khi chọn:

• Subarr1[] = {2, 4, 3}
• Subarr2[] = {3, 3, 12}

Thuật toán

Sử dụng công thức:

f(a, 1, n) + f(b, 1, n)

Trong đó f là phép toán OR bitwise trên toàn bộ mảng.

Chương trình C++

#include <bits/stdc++.h> 
using namespace std; 

int getMaximumSum(int *arr1, int *arr2, int n) {
    int sum1 = 0;
    int sum2 = 0;
    for (int i = 0; i < n; ++i) {
        sum1 = sum1 | arr1[i];
        sum2 = sum2 | arr2[i];
    }
    return sum1 + sum2;
}

int main() {
    int arr1[] = {1, 2, 4, 3, 2};
    int arr2[] = {1, 3, 3, 12, 2};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Maximum result = " << getMaximumSum(arr1, arr2, n) << endl;
    return 0;
}

Kết quả

Maximum result = 22

Giải thích

Phép OR bitwise tích lũy tất cả các bit được bật trong mảng. Tổng lớn nhất đạt được khi lấy OR của toàn bộ mảng vì mở rộng mảng con không bao giờ giảm giá trị OR.