Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Maximum Subarray XOR

Maximum Subarray XOR

Solve a hard-level problem for finding the maximum subarray XOR value in an array using tries.

We'll cover the following...

Problem statement

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

Example 1

Sample input

nums: [1,2,3,4]

Sample output

7

Explanation

The subarray [3, 4] has maximum XOR value of 7.

Example 2

Sample input

[8,1,2,12,7,6]

Sample output

15

Explanation

The subarray [1,2,12] has the maximum XOR value of 15.

Try it yourself

Try to solve the problem yourself before reading the solution.

#include <iostream>

#include <vector>

using namespace std;



int maxSubarrayXOR(vector<int> nums) {

  // your code goes here

  return -1;

}

Intuition

A brute force solution finds the XOR of all possible subarrays and then extracts the maximum value. We iterate from i=0i=0 to N−1N-1 and in a nested loop from j=ij=i to N−1N-1. The value of jj determines the end point for the current subarray starting from ii. When we calculate the XOR value for each subarray and update the maximum value, the maximum value at the end is the required answer.

#include<bits/stdc++.h>
using namespace std;
int maxSubarrayXOR(vector<int> nums) {
	// Initialize result
	int ans = INT_MIN;	 
	// Pick starting points of subarrays
	for (int i=0; i<nums.size(); i++) { 
		// to store xor of current subarray
		int currXOR = 0; 
		// Pick ending points of subarrays starting with i
		for (int j=i; j<nums.size(); j++) {
			currXOR = currXOR ^ nums[j];
			ans = max(ans, currXOR);
		}
	}
	return ans;
}
// Driver program to test maxSubarrayXOR function
int main() {
	vector<int> nums = {8, 1, 2, 12};
	cout << maxSubarrayXOR(nums);
	return 0;
}
Brute force solution in C++

Complexity analysis

In the above code, we iterate over the input array in a nested loop, resulting in a time complexity of O(N2)O(N^2), where NN is the size of the input array.

Only a single variable, currXOR, is created to store the final answer. So the ...

Access this course and 1400+ top-rated courses and projects.