Shubham and Subarray Xor

4.4

5 votes
Advanced Data Structures, Data Structures, Medium, Tries, medium
Problem

You are given an array consisting of n integers a1,a2,..an. Find the maximum value of xor of sum of 2 disjoint subarrays i.e maximize ( sum(l1,r1) xor sum(l2,r2) )
where 1l1r1 < l2r2n.
Note: sum(l,r) denotes sum of elements from indices l to r both inclusive.

Input Format
First line contains number n denoting the number of array elements.
Second line contains n integers denoting a1,a2,..an.

Output Format
Output the required value.

Constraints
1n900
1ai100

Time Limit: 1
Memory Limit: 257
Source Limit:
Explanation

The optimal values of l1,r1,l2,r2 are 1,2,3,4.
Sum(1,2) = 1 + 2 = 3
Sum(3,4) = 1 + 3 = 4
Sum(1,2) xor Sum(3,4) = 7.
Note that you cannot get a value greater than 7.

Editor Image

?