Tìm dãy con với AND và OR bitwise lớn nhất trong Python

Cho mảng n phần tử. Chọn 2 dãy con (có thể trùng nhau) để tổng (AND của dãy 1) + (OR của dãy 2) lớn nhất.

Ví dụ: A=[4,6,7,2] → max AND = 7 (chọn [7]), max OR = 7 (chọn tất cả 4|6|7|2=7) → kết quả 14.

Giải thuật

• Max AND của dãy con = max phần tử mảng (chọn dãy 1 phần tử là max).
• Max OR của dãy con = OR của toàn bộ mảng (OR đơn điệu tăng khi thêm phần tử).
• Kết quả = max(arr) | (OR toàn mảng).

Ví dụ

def get_max_sum(arr):
    and_max = max(arr)
    or_max = 0
    for x in arr:
        or_max |= x
    return and_max + or_max

a = [4, 6, 7, 2]
print(get_max_sum(a))

Đầu vào

[4,6,7,2]

Đầu ra

14