All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Shubham and Subarray Xor
/

Advanced Data Structures, Data Structures, Tries, medium

Problem
Editorial
Analytics

You are given an array consisting of n integers \(a_1,a_2,..a_n\). Find the maximum value of xor of sum of 2 disjoint subarrays i.e maximize ( sum(\(l_1,r_1\)) xor sum(\(l_2,r_2\)) )
where \(1\le l_1\le r_1 \) < \(l_2\le r_2\le n\).
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 \(a_1,a_2,..a_n\).

Output Format
Output the required value.

Constraints
\(1\le n\le 900 \)
\(1\le a_i\le 100 \)

SAMPLE INPUT
4
1 2 1 3
SAMPLE OUTPUT
7
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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 257 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?