Subarray Removal Codechef Solution

Problem

Chef has a binary array $A$ of length $N$. In one operation, Chef does the following:

1. Select any $L$ and $R$ such that $(1\le L<R\le |A|)$\\2. Add A_L \oplus A_{L+1} \oplus \ldots \oplus A_RAL​⊕AL+1​⊕…⊕AR​ to his score (Here, $\oplus$ denotes the bitwise XOR operation)\\3. Remove the subarray A_{L \dots R}AL…R​ from $A$

Determine the maximum score Chef can get after performing the above operation any number of times.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the size of the array $A$.
• The second line of each test case contains $N$ space-separated integers A_1, A_2, \dots, A_NA1​,A2​,…,AN​ denoting the array $A$.

Output Format

For each test case, output the maximum score Chef can get.

Constraints

Sample 1:

3
5
1 0 0 0 1
3
1 1 1
3
0 0 0

2
1
0

Explanation:

Test Case 1: We can perform the following moves:

• $A=[1,0,0,0,1]$. Select $L=1$ and $R=3$ and remove subarray $[1,0,0]$. $A$ becomes $[0,1]$.
• $A=[0,1]$. Select $L=1$ and $R=2$ and remove subarray $[0,1]$. $A$ becomes $[]$.

Total score $=1+1=2$

Test Case 2: We can perform the following move:

• $A=[1,1,1]$. Select $L=1$ and $R=3$ and remove subarray $[1,1,1]$. $A$ becomes $[]$.

Total score $=1$