题目正确题意
给你一个整数数组 nums 和正整数 k ，需要选出长度为 2*k 的子序列，将其均分为前后各 k 个元素：
- 前半段所有元素做按位或得到值 A
- 后半段所有元素做按位或得到值 B
- 序列值 = A XOR B
求所有合法子序列中的最大序列值 。
核心观察
- 数值范围： 1 <= nums[i] < 2^7 = 128 ，因此任意个元素按位或的结果最多只有 128 种可能，这是优化的关键。
- 采用前后缀DP + 枚举分割点的思路：预处理前缀选j个的所有可能或值、后缀选j个的所有可能或值，再枚举前后段的分割点，遍历所有或值组合求异或最大值。
Java 完整实现
java
public class Solution {
public int maxValue(int[] nums, int k) {
int n = nums.length;
final int MAX_VAL = 1 << 7; // 数值小于128，或结果最多128种
// pre[i][j][v]：前i个元素中选j个，按位或结果为v是否可达
boolean[][][] pre = new boolean[n + 1][k + 1][MAX_VAL];
pre[0][0][0] = true;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= k; j++) {
// 不选当前元素，直接继承前i-1个的结果
System.arraycopy(pre[i - 1][j], 0, pre[i][j], 0, MAX_VAL);
// 选当前元素，从j-1个的状态转移
if (j > 0) {
for (int v = 0; v < MAX_VAL; v++) {
if (pre[i - 1][j - 1][v]) {
pre[i][j][v | num] = true;
}
}
}
}
}
// suf[i][j][v]：从下标i到数组末尾选j个，按位或结果为v是否可达
boolean[][][] suf = new boolean[n + 1][k + 1][MAX_VAL];
suf[n][0][0] = true;
for (int i = n - 1; i >= 0; i--) {
int num = nums[i];
for (int j = 0; j <= k; j++) {
// 不选当前元素，继承后i+1个的结果
System.arraycopy(suf[i + 1][j], 0, suf[i][j], 0, MAX_VAL);
// 选当前元素，从j-1个的状态转移
if (j > 0) {
for (int v = 0; v < MAX_VAL; v++) {
if (suf[i + 1][j - 1][v]) {
suf[i][j][v | num] = true;
}
}
}
}
}
int ans = 0;
// 枚举分割点：前split个元素选k个，后n-split个元素选k个
for (int split = k; split <= n - k; split++) {
boolean[] leftOr = pre[split][k];
boolean[] rightOr = suf[split][k];
// 遍历所有可能的或值组合，求异或最大值
for (int a = 0; a < MAX_VAL; a++) {
if (leftOr[a]) {
for (int b = 0; b < MAX_VAL; b++) {
if (rightOr[b]) {
ans = Math.max(ans, a ^ b);
}
}
}
}
}
return ans;
}
}
复杂度分析
1. 时间复杂度：O(n * k * 128 + n * 128²)
- 前后缀DP：各 O(nk128)，n最大400、k最大200、128是值域上限，计算量极低。
- 枚举分割点求最大值：最多n个分割点，每个点最多128*128次异或运算，总开销可忽略。
2. 空间复杂度：O(n * k * 128)，使用三维布尔数组存储可达状态。
思路补充
- 按位或的性质：选的元素越多，或结果不会变小，且值域被限制在128以内，因此用布尔数组标记可达结果比集合更高效。
- 分割点的意义：保证前半段和后半段的元素完全不重叠，对应子序列的前后k个元素来自数组不同区间，天然满足子序列的下标递增要求。
需要我补充空间优化版的一维DP实现吗？
