#3277
Hard Algorithms Maximum xor score subarray queries
Array Dynamic Programming
43.7% acceptance
Feb 25, 2026
109
16
You are given nums[0..n-1] and queries[i]=[li,ri].
XOR score of array a: repeatedly replace a[i] with a[i]^a[i+1] for all i except last, then remove last.
Find the maximum XOR score of any subarray of nums[li..ri].
Solution
Rust
Time O(n * m)
Space O(n * m)
impl Solution {
pub fn maximum_subarray_xor(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let n = nums.len();
// xor_val[l][r] = XOR score of subarray nums[l..=r]
// Property: xor_val[l][r] = xor_val[l][r-1] ^ xor_val[l+1][r]
// Base: xor_val[i][i] = nums[i]
let mut xv = vec![vec![0i32; n]; n];
for i in 0..n {
xv[i][i] = nums[i];
}
for len in 2..=n {
for l in 0..=(n - len) {
let r = l + len - 1;
xv[l][r] = xv[l][r - 1] ^ xv[l + 1][r];
}
}
// max_xv[l][r] = max xor_val over all subranges [l'..r'] ⊆ [l,r]
let mut mx = vec![vec![0i32; n]; n];
for i in 0..n {
mx[i][i] = nums[i];
}
for len in 2..=n {
for l in 0..=(n - len) {
let r = l + len - 1;
mx[l][r] = xv[l][r].max(mx[l][r - 1]).max(mx[l + 1][r]);
}
}
queries
.iter()
.map(|q| mx[q[0] as usize][q[1] as usize])
.collect()
}
}