Search⌘ K
Home
Courses
Advanced Data Structures: Implementing Tries in C++ and Java

Maximum Subarray XOR

Explore how to solve the maximum subarray XOR problem by leveraging bitwise tries for efficient XOR computations. Understand algorithm design, binary representation, and how to implement the solution with optimal time and space complexity in C++ and Java.

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.

C++
Java
#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.

C++
Java
#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 overall space complexity remains constant—that is, ...