javaclass Solution {public long maximizeXorAndXor(int[] nums) {int n nums.length;int totalMasks 1 n; // 2^nint allMask totalMasks - 1;// 预计算所有子集的按位与、异或和或的值int[] andVal new int[totalMasks];int[] xorVal new int[totalMasks];int[] orVal new int[totalMasks];// 空集异或0或0与用-1占位后续再修正为0andVal[0] -1;xorVal[0] 0;orVal[0] 0;for (int mask 1; mask totalMasks; mask) {// 提取最低位的1int 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];}// 将空集的与修正为0andVal[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但剪枝后实际运行会快很多。
