Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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()
  }
}