LeetCode 题解工作台
求出数组中最大序列值
给你一个整数数组 nums 和一个 正 整数 k 。 定义长度为 2 * x 的序列 seq 的 值 为： (seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1]) . 请你…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们考虑将序列分成两部分，前 个元素和后 个元素，分别计算前后缀的所有可能的异或值。 定义 表示前 个元素中取 个元素，是否存在一个子集的异或值为 ，定义 表示从下标 开始取 个元素，是否存在一个子集的异或值为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 nums 和一个 正 整数 k 。
定义长度为 2 * x 的序列 seq 的 值 为：
(seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1]).
请你求出 nums 中所有长度为 2 * k 的 子序列 的 最大值 。
示例 1：
输入：nums = [2,6,7], k = 1
输出：5
解释：
子序列 [2, 7] 的值最大，为 2 XOR 7 = 5 。
示例 2：
输入：nums = [4,2,5,6,7], k = 2
输出：2
解释：
子序列 [4, 5, 6, 7] 的值最大，为 (4 OR 5) XOR (6 OR 7) = 2 。
提示：
2 <= nums.length <= 4001 <= nums[i] < 271 <= k <= nums.length / 2
解题思路
方法一：动态规划 + 前后缀分解 + 枚举
我们考虑将序列分成两部分，前 个元素和后 个元素，分别计算前后缀的所有可能的异或值。
定义 表示前 个元素中取 个元素，是否存在一个子集的异或值为 ，定义 表示从下标 开始取 个元素，是否存在一个子集的异或值为 。
考虑 的转移方程，对于第 个元素（从 开始），我们可以选择不取，也可以选择取，因此有：
对于 的转移方程，同样对于第 个元素（从 开始），我们可以选择不取，也可以选择取，因此有：
最后，我们在 的范围内枚举 ，对于每一个 ，我们枚举 和 ，其中 ，如果 和 均为真，那么我们更新答案 。
时间复杂度 ，空间复杂度 ，其中 为数组长度，而 。
class Solution:
def maxValue(self, nums: List[int], k: int) -> int:
m = 1 << 7
n = len(nums)
f = [[[False] * m for _ in range(k + 2)] for _ in range(n + 1)]
f[0][0][0] = True
for i in range(n):
for j in range(k + 1):
for x in range(m):
f[i + 1][j][x] |= f[i][j][x]
f[i + 1][j + 1][x | nums[i]] |= f[i][j][x]
g = [[[False] * m for _ in range(k + 2)] for _ in range(n + 1)]
g[n][0][0] = True
for i in range(n, 0, -1):
for j in range(k + 1):
for y in range(m):
g[i - 1][j][y] |= g[i][j][y]
g[i - 1][j + 1][y | nums[i - 1]] |= g[i][j][y]
ans = 0
for i in range(k, n - k + 1):
for x in range(m):
if f[i][k][x]:
for y in range(m):
if g[i][k][y]:
ans = max(ans, x ^ y)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on iterating through all elements and possible k-length OR combinations, roughly O(n * k * 2^m) for bit states. Space complexity is O(n * k) for DP storage with optimization possible via rolling arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may hint at optimizing bitwise operations rather than naive pair checking.
- question_mark
Expect prompts about state definition for dynamic programming and handling OR/XOR transitions.
- question_mark
Clarifications may focus on array length constraints and avoiding recomputation across subsequences.
常见陷阱
外企场景- error
Forgetting to consider all OR combinations leading to suboptimal maximum.
- error
Mismanaging DP state transitions causing index out-of-bounds errors.
- error
Assuming XOR distribution is linear without correctly pairing OR segments.
进阶变体
外企场景- arrow_right_alt
Compute maximum subsequence value with additional sum constraints alongside OR/XOR evaluation.
- arrow_right_alt
Allow subsequences of variable even lengths instead of strictly 2 * k.
- arrow_right_alt
Modify operations to include AND or custom bitwise operations while maintaining state transition DP.