What is the main pattern used in Maximum XOR Score Subarray Queries?

The core pattern is state transition dynamic programming, which precomputes subarray XOR scores and updates efficiently across queries.

Can prefix XOR reduce space complexity in this problem?

Yes, using prefix XOR allows O(n) space while still computing subarray XOR in O(1) time, avoiding a full O(n^2) DP table.

Why can't we compute XOR on the fly for each query?

Computing XOR on the fly leads to redundant calculations and results in TLE for large arrays due to the quadratic number of subarrays.

Does this problem require handling overlapping subarrays?

Yes, state transition dynamic programming handles overlapping subarrays efficiently by reusing previously computed XOR scores.

What is a common mistake when implementing this solution?

A common mistake is ignoring XOR's associative property, leading to incorrect accumulation when combining subarrays or misapplying DP updates.

#3277

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

查询子数组最大异或值

给你一个由 n 个整数组成的数组 nums ，以及一个大小为 q 的二维整数数组 queries ，其中 queries[i] = [l i , r i ] 。对于每一个查询，你需要找出 nums[l i ..r i ] 中任意子数组的最大异或值。数组的异或值需要对数组 a 反复执行以…

数组动态规划

题目描述

给你一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维整数数组 queries，其中 queries[i] = [l_i, r_i]。

对于每一个查询，你需要找出 nums[l_i..r_i] 中任意子数组的 最大异或值。

数组的异或值 需要对数组 a 反复执行以下操作，直到只剩一个元素，剩下的那个元素就是 异或值：

对于除最后一个下标以外的所有下标 i，同时将 a[i] 替换为 a[i] XOR a[i + 1] 。
移除数组的最后一个元素。

返回一个大小为 q 的数组 answer，其中 answer[i] 表示查询 i 的答案。

示例 1：

输入： nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]

输出： [12,60,60]

解释：

在第一个查询中，nums[0..2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，所有异或值中的最大值。

在第二个查询中，nums[1..4] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

在第三个查询中，nums[0..5] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

示例 2：

输入： nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

输出： [7,14,11,14,5]

解释：

下标	nums[l_i..r_i]	最大异或值子数组	子数组最大异或值
0	[0, 7, 3, 2]	[7]	7
1	[7, 3, 2, 8, 5]	[7, 3, 2, 8]	14
2	[3, 2, 8]	[3, 2, 8]	11
3	[3, 2, 8, 5, 1]	[2, 8, 5, 1]	14
4	[5, 1]	[5]	5

提示：

1 <= n == nums.length <= 2000
0 <= nums[i] <= 2³¹ - 1
1 <= q == queries.length <= 10⁵
queries[i].length == 2
queries[i] = [l_i, r_i]
0 <= l_i <= r_i <= n - 1

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示 $\textit{nums}[i..j]$ 的异或值，那么根据题目描述，我们可以得到状态转移方程：

f[i][j] = f[i][j-1] \oplus f[i+1][j]

其中 $\oplus$ 表示异或运算。

我们再定义 $g[i][j]$ 表示 $f[i][j]$ 的最大值，那么状态转移方程为：

g[i][j] = \max(f[i][j], g[i][j-1], g[i+1][j])

最后，我们遍历查询数组，对于每个查询 $[l, r]$ ，将 $g[l][r]$ 加入答案数组即可。

时间复杂度 $O(n^2 + m)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 和 $m$ 分别为数组 $\textit{nums}$ 和 $\textit{queries}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maximumSubarrayXor(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        n = len(nums)
        f = [[0] * n for _ in range(n)]
        g = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            f[i][i] = g[i][i] = nums[i]
            for j in range(i + 1, n):
                f[i][j] = f[i][j - 1] ^ f[i + 1][j]
                g[i][j] = max(f[i][j], g[i][j - 1], g[i + 1][j])
        return [g[l][r] for l, r in queries]

speed

复杂度分析

指标	值
时间	complexity depends on precomputing the DP table, which is O(n^2), and answering q queries using precomputed states is O(1) per subarray access. Space complexity is O(n^2) for the DP table, though prefix XOR optimizations can reduce space to O(n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you precompute subarray XOR scores to save repeated calculations.
question_mark
Looks for use of dynamic programming to handle overlapping subarray states efficiently.
question_mark
Wants recognition of XOR properties to optimize computation for multiple queries.

warning

常见陷阱

外企场景

error
Attempting to compute XOR scores on the fly without DP, leading to TLE for large n.
error
Misapplying the state transition logic and incorrectly combining subarrays.
error
Ignoring the associative property of XOR, which can simplify computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximum XOR score for all subarrays without queries, returning a single global max.
arrow_right_alt
Queries asking for minimum XOR score subarrays instead of maximum.
arrow_right_alt
Applying the same DP approach for XOR with other operations like sum or AND.

help

常见问题

外企场景

继续练习

#3276 选择矩阵中单元格的最大得分 #3287 求出数组中最大序列值 #3290 最高乘法得分