Hard
题目描述
给你一个整数数组 nums。
将数组划分为三个（可能为空的）子序列 A、B 和 C，使得 nums 的每个元素恰好属于一个子序列。
你的目标是最大化以下值：XOR(A) + AND(B) + XOR(C)
其中：
XOR(arr)表示数组arr中所有元素的按位异或。如果arr为空，则其值定义为 0。AND(arr)表示数组arr中所有元素的按位与。如果arr为空，则其值定义为 0。
返回可达到的最大值。
注意：如果多个划分结果具有相同的最大和，你可以考虑其中任何一个。
示例 1：
输入：nums = [2,3]
输出：5
解释：
一个最优划分是：
- A = [3], XOR(A) = 3
- B = [2], AND(B) = 2
- C = [], XOR(C) = 0
最大值：XOR(A) + AND(B) + XOR(C) = 3 + 2 + 0 = 5
示例 2：
输入：nums = [1,3,2]
输出：6
解释：
一个最优划分是：
- A = [1], XOR(A) = 1
- B = [2], AND(B) = 2
- C = [3], XOR(C) = 3
最大值：XOR(A) + AND(B) + XOR(C) = 1 + 2 + 3 = 6
示例 3：
输入：nums = [2,3,6,7]
输出：15
解释：
一个最优划分是：
- A = [7], XOR(A) = 7
- B = [2,3], AND(B) = 2
- C = [6], XOR(C) = 6
最大值：XOR(A) + AND(B) + XOR(C) = 7 + 2 + 6 = 15
约束条件：
1 <= nums.length <= 191 <= nums[i] <= 10^9
解题思路
这是一道复杂的位运算优化问题，需要综合运用贪心策略和线性基（XOR Basis）技巧。
核心思路：
枚举子集B：由于数组长度最多19，我们可以暴力枚举所有可能的子集B（2^19种可能）。
数学变换：对于固定的B，设剩余元素的异或值为s = XOR(所有不在B中的元素)。我们需要将剩余元素划分为A和C，使得XOR(A) + XOR(C)最大。设XOR(A) = x，则XOR(C) = s ⊕ x。
关键观察：我们要最大化 x + (s ⊕ x)。通过位运算性质可以证明：x + (s ⊕ x) = s + 2 × (x & ~s)。这意味着我们需要最大化 x & ~s。
线性基优化：为了高效找到最大的 x & ~s，我们构建一个线性基。对于每个不在B中的元素nums[j]，将nums[j] & ~s加入线性基。然后贪心地从高位到低位提取最大值。
线性基贪心：线性基是一组向量，可以表示所有可能的异或组合。通过维护每个位的基向量，我们可以在O(log V)时间内找到最大异或值。
这种方法的时间复杂度是O(n × 2^n × log V)，其中V是数值范围，在给定约束下是可接受的。
推荐解法：枚举子集B + 线性基优化，这是最优且最清晰的解法。
代码实现
class Solution {
public:
long long maximizeXorAndXor(vector<int>& nums) {
int n = nums.size();
long long maxVal = 0;
// 枚举所有可能的子集B
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> remaining;
long long andB = 0;
bool first = true;
// 计算B的AND值和剩余元素
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
if (first) {
andB = nums[i];
first = false;
} else {
andB &= nums[i];
}
} else {
remaining.push_back(nums[i]);
}
}
if (mask != 0 && andB == 0) continue; // B非空但AND为0，跳过
// 计算剩余元素的总异或
long long s = 0;
for (int x : remaining) {
s ^= x;
}
// 构建线性基
vector<long long> basis(60, 0);
for (int x : remaining) {
long long val = x & (~s);
for (int bit = 59; bit >= 0; bit--) {
if (!(val & (1LL << bit))) continue;
if (!basis[bit]) {
basis[bit] = val;
break;
}
val ^= basis[bit];
}
}
// 贪心提取最大值
long long maxXor = 0;
for (int bit = 59; bit >= 0; bit--) {
maxXor = max(maxXor, maxXor ^ basis[bit]);
}
maxVal = max(maxVal, andB + s + 2 * maxXor);
}
return maxVal;
}
};
class Solution:
def maximizeXorAndXor(self, nums: List[int]) -> int:
n = len(nums)
max_val = 0
# 枚举所有可能的子集B
for mask in range(1 << n):
remaining = []
and_b = 0
first = True
# 计算B的AND值和剩余元素
for i in range(n):
if mask & (1 << i):
if first:
and_b = nums[i]
first = False
else:
and_b &= nums[i]
else:
remaining.append(nums[i])
if mask != 0 and and_b == 0:
continue # B非空但AND为0，跳过
# 计算剩余元素的总异或
s = 0
for x in remaining:
s ^= x
# 构建线性基
basis = [0] * 60
for x in remaining:
val = x & (~s)
for bit in range(59, -1, -1):
if not (val & (1 << bit)):
continue
if not basis[bit]:
basis[bit] = val
break
val ^= basis[bit]
# 贪心提取最大值
max_xor = 0
for bit in range(59, -1, -1):
max_xor = max(max_xor, max_xor ^ basis[bit])
max_val = max(max_val, and_b + s + 2 * max_xor)
return max_val
public class Solution {
public long MaximizeXorAndXor(int[] nums) {
int n = nums.Length;
long maxVal = 0;
// 枚举所有可能的子集B
for (int mask = 0; mask < (1 << n); mask++) {
List<int> remaining = new List<int>();
long andB = 0;
bool first = true;
// 计算B的AND值和剩余元素
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
if (first) {
andB = nums[i];
first = false;
} else {
andB &= nums[i];
}
} else {
remaining.Add(nums[i]);
}
}
if (mask != 0 && andB == 0) continue; // B非空但AND为0，跳过
// 计算剩余元素的总异或
long s = 0;
foreach (int x in remaining) {
s ^= x;
}
// 构建线性基
long[] basis = new long[60];
foreach (int x in remaining) {
long val = x & (~s);
for (int bit = 59; bit >= 0; bit--) {
if ((val & (1L << bit)) == 0) continue;
if (basis[bit] == 0) {
basis[bit] = val;
break;
}
val ^= basis[bit];
}
}
// 贪心提取最大值
long maxXor = 0;
for (int bit = 59; bit >= 0; bit--) {
maxXor = Math.Max(maxXor, maxXor ^ basis[bit]);
}
maxVal = Math.Max(maxVal, andB + s + 2 * maxXor);
}
return maxVal;
}
}
var maximizeXorAndXor = function(nums) {
const n = nums.length;
let maxSum = 0;
// Try all possible partitions using bitmask
// 0: A, 1: B, 2: C
function backtrack(index, A, B, C) {
if (index === n) {
const xorA = A.length === 0 ? 0 : A.reduce((acc, val) => acc ^ val, 0);
const andB = B.length === 0 ? 0 : B.reduce((acc, val) => acc & val);
const xorC = C.length === 0 ? 0 : C.reduce((acc, val) => acc ^ val, 0);
maxSum = Math.max(maxSum, xorA + andB + xorC);
return;
}
// Try putting nums[index] in A
A.push(nums[index]);
backtrack(index + 1, A, B, C);
A.pop();
// Try putting nums[index] in B
B.push(nums[index]);
backtrack(index + 1, A, B, C);
B.pop();
// Try putting nums[index] in C
C.push(nums[index]);
backtrack(index + 1, A, B, C);
C.pop();
}
backtrack(0, [], [], []);
return maxSum;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n × 2^n × log V) |
| 空间复杂度 | O(n + log V) |
其中 n 是数组长度，V 是数值范围（约10^9）。枚举子集需要 O(2^n)，每个子集处理需要 O(n + log V)。