Shubham and Subarray Xor
Tag(s):

## Advanced Data Structures, Data Structures, Medium, Trie (Keyword Tree), 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

January Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Data Structures > Hash Tables
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming

?