Problem 52: Maximum Bitwise OR Subarray
Problem Statement: Given an array of non-negative integers, determine the maximum bitwise OR obtainable from any non-empty contiguous subarray.
Input
The first line contains an integer n, the number of elements. The second line contains n space-separated non-negative integers.
Output
Print the maximum possible value obtained by the bitwise OR of all elements in some contiguous subarray.
Examples
Input:
5
1 2 4 0 3
Output:
7
Solution Explanation
A brute-force approach examines every subarray and computes its bitwise OR (O(n^2)). Optimization can be done using the idea that OR is cumulative; however, in worst-case scenarios an O(n^2) solution suffices given moderate constraints.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
int ans = 0;
for(int i = 0; i < n; i++){
int cur = 0;
for(int j = i; j < n; j++){
cur |= a[j];
ans = max(ans, cur);
}
}
cout << ans << "\n";
return 0;
}