Maximum OR Sum of Sub-arrays: ผลรวม OR สูงสุดของ Sub-arrays สองอาร์เรย์ใน C++

ปัญหา

กำหนดอาร์เรย์ 2 ตัว arr1, arr2 เลือก Subarray ขนาดเท่ากันจากแต่ละอาร์เรย์ ให้ OR Sum = (OR ของ Subarray1) + (OR ของ Subarray2) สูงสุด

ตัวอย่าง: arr1=[1,2,4,3,2], arr2=[1,3,3,12,2] → Subarrays: [2,4,3] และ [3,3,12] → OR1=7, OR2=15 → Sum=22

ข้อสังเกตสำคัญ

OR Operation เป็น Monotonic: เพิ่ม Element เข้าไป OR จะคงที่หรือเพิ่มขึ้น (ไม่เคยลด)

→ OR ของทั้งอาร์เรย์ = ค่าสูงสุดที่เป็นไปได้ สำหรับ Subarray ใดๆ

→ คำตอบ = OR(arr1) + OR(arr2) (เลือกทั้งอาร์เรย์)

โค้ด C++

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

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

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);  // 22
    return 0;
}

การคำนวณตัวอย่าง

arr1: 1 | 2 | 4 | 3 | 2
      001
      010
      100
      011
      010
OR = 111₂ = 7

arr2: 1 | 3 | 3 | 12 | 2
      0001
      0011
      0011
      1100
      0010
OR = 1111₂ = 15

Sum = 7 + 15 = 22

ความซับซ้อน

• Time: O(n)
• Space: O(1)

Input / Output

Input:  arr1=[1,2,4,3,2], arr2=[1,3,3,12,2]
Output: Maximum result = 22