问题分析

异或分数定义：对数组反复执行操作——同时将 a[i] 替换为 a[i] XOR a[i+1]，并移除最后一个元素，直到只剩一个元素。

核心规律：子数组 nums[i..j] 的异或分数满足递推式：

```
f[i][j] = f[i][j-1] XOR f[i+1][j]
```

其中 f[i][i] = nums[i]。

这类似于杨辉三角的异或版本——每个区间的分数由其左区间和右区间的分数异或得到。

对于每个查询 [l, r]，答案是在 nums[l..r] 范围内所有子数组的异或分数中的最大值。

---

解法思路：双层区间DP

第一步：计算所有子数组的异或分数

用二维数组 xorScore[i][j] 表示子数组 nums[i..j] 的异或分数。

递推：xorScore[i][j] = xorScore[i][j-1] ^ xorScore[i+1][j]

第二步：计算所有区间内子数组的最大异或分数

用二维数组 maxScore[i][j] 表示在 nums[i..j] 范围内，所有子数组的异或分数的最大值。

递推：maxScore[i][j] = max(xorScore[i][j], maxScore[i][j-1], maxScore[i+1][j])

遍历顺序

由于递推依赖 i+1 和 j-1，需要按区间长度从小到大遍历，或者 i 从 n-1 到 0 倒序、j 从 i+1 到 n-1 正序。

---

Java实现

```java
class Solution {
    public int[] maximumSubarrayXor(int[] nums, int[][] queries) {
        int n = nums.length;
        
        // xorScore[i][j]: 子数组 nums[i..j] 的异或分数
        int[][] xorScore = new int[n][n];
        // maxScore[i][j]: nums[i..j] 范围内所有子数组的最大异或分数
        int[][] maxScore = new int[n][n];
        
        // 初始化长度为1的子数组
        for (int i = 0; i < n; i++) {
            xorScore[i][i] = nums[i];
            maxScore[i][i] = nums[i];
        }
        
        // 按区间长度从小到大递推
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                // 计算异或分数
                xorScore[i][j] = xorScore[i][j - 1] ^ xorScore[i + 1][j];
                // 计算最大分数
                maxScore[i][j] = Math.max(xorScore[i][j],
                                   Math.max(maxScore[i][j - 1], maxScore[i + 1][j]));
            }
        }
        
        // 处理所有查询
        int q = queries.length;
        int[] ans = new int[q];
        for (int k = 0; k < q; k++) {
            int l = queries[k][0];
            int r = queries[k][1];
            ans[k] = maxScore[l][r];
        }
        return ans;
    }
}
```

---

复杂度分析

指标 复杂度
时间复杂度 O(n² + q)
空间复杂度 O(n²)

其中 n 为数组长度（n ≤ 2000），q 为查询数量（q ≤ 10⁵）。每个查询 O(1) 回答。

---

示例验证

以 nums = [2,8,4,32,16,1]，查询 [0,2] 为例：

· 子数组 [2,8,4] 的异或分数 = xorScore[0][2] = 2 ^ 8 ^ 4 = 6（按递推计算）
· 范围内所有子数组的异或分数：[2]=2, [8]=8, [4]=4, [2,8]=10, [8,4]=12, [2,8,4]=6
· 最大值 = 12，与预期输出一致