Tổng HOẶC tối đa của các mảng con của hai mảng khác nhau trong C ++

Tuyên bố vấn đề

Cho hai mảng các số nguyên dương. Chọn hai mảng con có kích thước bằng nhau từ mỗi mảng và tính tổng OR tối đa có thể có 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ả tối đa thu được khi chúng ta tạo hai mảng con sau -

Subarr1 [] ={2, 4, 3} và

Subarr2 [] ={3, 3, 12}

Thuật toán

Chúng ta có thể sử dụng công thức dưới đây để nhận được kết quả -

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

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Maximum result = 22