# Maximum Subarray VI

# Question

Given an array of integers. find the maximum XOR subarray value in given array.

What's the XOR: https://en.wikipedia.org/wiki/Exclusive_or

# Notice

Expected time complexity O(n).

# Answer

https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

Let's say F(L,R) is XOR of subarray from L to R.

Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1). How?

Let's say our subarray with maximum XOR ended at position i. Now, we need to maximise F(L,i) ie. F(1,i) XOR F(1,L-1) where L<=i. Suppose, we inserted F(1,L-1) in our trie for all L<=i, then it's just problem1.

```
class Solution {
public:
/*
* @param : the array
* @return: the max xor sum of the subarray in a given array
*/
int maxXorSubarray(vector<int> &nums) {
// write code here
int ans = INT_MIN;
int pre = 0;
Trie trie;
for (auto n : nums) {
pre = pre ^ n;
trie.insert(pre);
ans = max(ans, trie.query(pre));
}
return ans;
}
private:
class Trie {
public:
Trie() {
root = new TrieNode(0);
INTBITS = sizeof(int) * 8;
}
void insert(int x) {
TrieNode* iter = root;
for (int i = INTBITS - 1; i >= 0; i--) {
bool v = x & (1 << i);
if (iter->arr[v] == 0)
iter->arr[v] = new TrieNode(0);
iter = iter->arr[v];
}
iter->val = x;
}
int query(int x) {
TrieNode* iter = root;
for (int i = INTBITS - 1; i >= 0; i--) {
bool v = x & (1 << i);
if (iter->arr[1-v] != 0)
iter = iter->arr[1-v];
else if (iter->arr[v] != 0)
iter = iter->arr[v];
}
return x ^ iter->val;
}
private:
class TrieNode {
public:
int val;
TrieNode *arr[2];
TrieNode(int v)
: val(v) {
arr[0] = arr[1] = 0;
}
};
TrieNode* root;
int INTBITS;
};
};
```