Bitwise OR Subarray Sum
HardPractice library · +30 XPbit manipulationprefix sumsdata structures
Given an array of N integers, find the maximum bitwise OR sum among all possible contiguous subarrays. A subarray is defined by a start and end index (inclusive). The bitwise OR sum of a subarray is the bitwise OR of all elements within that subarray.
Input
The first line contains an integer N. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print a single integer, the maximum bitwise OR sum found among all contiguous subarrays.
Constraints
1 <= N <= 200000, 0 <= a_i < 2^30
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 1 2 4 8 16
Output
31
The maximum OR sum is 31 (1 | 2 | 4 | 8 | 16).
Example 2
Input
4 3 5 2 7
Output
7
Subarrays: [3]=3, [5]=5, [2]=2, [7]=7, [3,5]=7, [5,2]=7, [2,7]=7, [3,5,2]=7, [5,2,7]=7, [3,5,2,7]=7. Max is 7.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 4 8 16
Example 2 input
4 3 5 2 7