DeepSeek LeetCode 3630. 划分数组得到最大异或运算和与运算之和 Java实现

```java
class Solution {
public long maximizeXorAndXor(int[] nums) {
int n = nums.length;
int totalMasks = 1 << n; // 2^n
int allMask = totalMasks - 1;

// 预计算所有子集的按位与、异或和或的值
int[] andVal = new int[totalMasks];
int[] xorVal = new int[totalMasks];
int[] orVal = new int[totalMasks];

// 空集：异或=0，或=0，与用-1占位，后续再修正为0
andVal[0] = -1;
xorVal[0] = 0;
orVal[0] = 0;

for (int mask = 1; mask < totalMasks; mask++) {
// 提取最低位的1
int lb = mask & -mask;
int idx = Integer.numberOfTrailingZeros(lb);
int prev = mask ^ lb; // 移除该元素后的子集

xorVal[mask] = xorVal[prev] ^ nums[idx];
// 前一个子集为空时，与结果直接为该元素
andVal[mask] = (prev == 0) ? nums[idx] : (andVal[prev] & nums[idx]);
orVal[mask] = orVal[prev] | nums[idx];
}
// 将空集的与修正为0
andVal[0] = 0;

long best = 0;

// 枚举B子集
for (int bMask = 0; bMask < totalMasks; bMask++) {
int remainMask = allMask ^ bMask; // 分配给A和C的元素

// 剪枝：理论上界都无法超越当前最优则跳过
// maxAndB = andVal[bMask], max(A^C) <= OR(remain), 因为异或结果的每一位不会超过或运算
if (andVal[bMask] + (long) orVal[remainMask] * 2 - xorVal[remainMask] <= best) {
continue;
}

// 枚举A子集（A是remainMask的子集）
for (int aMask = remainMask; ; aMask = (aMask - 1) & remainMask) {
int cMask = remainMask ^ aMask;
long sum = (long) xorVal[aMask] + andVal[bMask] + xorVal[cMask];
if (sum > best) {
best = sum;
}
if (aMask == 0) break;
}
}

return best;
}
}
```

核心思路与复杂度

这道题数据范围n <= 19，是典型的状态压缩枚举题。

1. 解法思想

· 子集枚举：数组长度最大19，可以用位掩码表示每个元素属于哪个子集。枚举B子集的所有情况，再从剩余元素中枚举A子集，C自然确定。
· 预计算加速：提前算出所有子集的异或、与、或值，枚举时直接查表，避免重复计算。
· 剪枝优化：利用XOR(A) + XOR(C) <= OR(A∪C) * 2 - XOR(A∪C)这个上界进行剪枝，能跳过很多无效枚举。

2. 时间复杂度

· O(3^n)：枚举B (2^n)，枚举其子集A平均(3^n/2^n)，总枚举量3^n。n <= 19时约1.16e9，但剪枝后实际运行会快很多。