All Tracks Data Structures Advanced Data Structures Problem
SOLVE
LATER
Shubham and Subarray Xor
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 \)
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...
Contributor
This Problem was Asked in
OTHER PROBLEMS OF THIS CHALLENGE
-
Algorithms > Sorting
-
Data Structures > Hash Tables
-
Algorithms > Dynamic Programming
-
Algorithms > Dynamic Programming
