2026-01-04：划分数组得到最大异或运算和与运算之和。用go语言，给定一个整数数组 nums，将每个元素分别分配到三个（可以为空的）子序列 A、B、C 中（每个元素恰好属于一组）。

目标是最大化：A 中所有元素的按位异或值 + B 中所有元素的按位与值 + C 中所有元素的按位异或值。

约定空序列的异或或与结果为 0。返回能够得到的最大总和。

这里的“子序列”指在保持原数组相对顺序的前提下，通过删除若干元素得到的序列；若多种分配方式产生相同最大值，任选一种即可。

1 <= nums.length <= 19。

1 <= nums[i] <= 1000000000。

输入: nums = [2,3]。

输出: 5。

解释:

一个最优划分是：

A = [3], XOR(A) = 3

B = [2], AND(B) = 2

C = [], XOR© = 0

最大值为: XOR(A) + AND(B) + XOR© = 3 + 2 + 0 = 5。因此，答案是 5。

题目来自力扣3630。

💡 核心思路与步骤

1. 问题分析与暴力枚举基础

题目要求将数组中的每个元素分配到三个子序列（A、B、C）之一，目标是最大化 XOR(A) + AND(B) + XOR(C)。由于“子序列”需要保持相对顺序，但题目允许任意分配，实际上等价于为每个元素独立地选择三个标签之一（A, B, C）。对于一个长度为 n 的数组，总共有 $3^n$ 种分配方式。当 n=19 时，$3^{19}$ 约为12亿，直接完全枚举计算量过大。因此，代码的核心在于如何高效地枚举和计算。

2. 预处理所有子集信息

代码没有直接枚举 $3^n$ 种分配，而是巧妙地利用了位掩码技术。它将所有元素是否属于某个子序列的状态，用一个 n 位的二进制数 mask 来表示（1<<n 种状态）。通过动态规划的方式，预处理出每个子集 mask 的三种关键信息：

• and：该子集内所有元素的按位与值。
• xor：该子集内所有元素的异或值。
• or：该子集内所有元素的按位或值。

这个过程通过一个循环高效完成：遍历每个元素，然后更新包含该元素的所有子集的信息。这是动态规划中常见的子集DP技巧。

3. 枚举与剪枝策略

预处理完成后，问题转化为：如何将全集 U 划分成两个互补的子集 i 和 j（即 i | j = U 且 i & j = 0）。其中一个子集（例如 j）将作为候选的B序列，剩下的元素（子集 i）需要进一步分配给A和C序列以最大化 XOR(A) + XOR(C)。

关键的优化在于剪枝：

• 代码在枚举划分 (i, j) 时，会计算一个当前可能的最大值上界：p.and + subSum[j].or*2 - subSum[j].xor。
• 这个上界是基于数学性质的一个乐观估计。如果这个估计值小于或等于当前已知的最大答案 ans，那么对于当前的 (i, j) 划分，无论剩下的元素如何在A和C中分配，都不可能得到更大的结果，因此可以直接跳过，无需进行更耗时的计算。

4. 线性基求解最大异或和

对于无法被剪枝的划分，需要解决一个核心子问题：给定一个元素集合（对应子集 j），如何将其划分为两个子序列A和C，使得 XOR(A) + XOR(C) 最大。

这里用到了一个重要的数学结论：XOR(A) + XOR(C) 的最大值，等价于在这个元素集合的异或空间中找到一组基，并计算其最大异或值的两倍。代码使用线性基数据结构来高效解决这个“最大异或和”问题：

• 线性基插入：将每个元素（经过特定变换后）插入线性基，得到一组极大线性无关组。
• 贪心求最大值：基于线性基，从高位到低位贪心地选择，使异或结果最大。

最终，将 B 序列的与值、以及 A 和 C 序列带来的最大异或和贡献相加，得到当前划分下的总价值，并更新全局最大答案。

🧮 复杂度分析

• 总的时间复杂度：主要由预处理和主循环决定。
  • 预处理所有子集信息的时间复杂度为 $O(2^n)$。
  • 主循环需要枚举所有划分 (i, j)，其数量也是 $O(2^n)$。对于每个未被剪枝的划分，需要调用 maxXor2 函数，其内部包含一个遍历子集元素的循环（最坏 $O(n)$）和线性基操作（$O(n)$）。因此，最坏情况下的总时间复杂度为 $O(2^n * n)$。当 n=19 时，$2^{19}$ 约为52万，这个复杂度是可以接受的。
• 总的额外空间复杂度：主要用于存储预处理出的所有子集信息（subSum 数组），其大小为 $O(2^n)$。因此，空间复杂度也是 $O(2^n)$。

Go完整代码如下：

package main

import (
	"fmt"
	"math/bits"
	"slices"
)

// 线性基模板
type xorBasis []int

func (b xorBasis) insert(x int) {
	for x > 0 {
		i := bits.Len(uint(x)) - 1 // x 的最高位
		if b[i] == 0 {             // x 和之前的基是线性无关的
			b[i] = x // 新增一个基，最高位为 i
			return
		}
		x ^= b[i] // 保证参与 maxXor 的基的最高位是互不相同的，方便我们贪心
	}
	// 正常循环结束，此时 x=0，说明一开始的 x 可以被已有基表出，不是一个线性无关基
}

func (b xorBasis) maxXor() (res int) {
	// 从高到低贪心：越高的位，越必须是 1
	// 由于每个位的基至多一个，所以每个位只需考虑异或一个基，若能变大，则异或之
	for i := len(b) - 1; i >= 0; i-- {
		res = max(res, res^b[i])
	}
	return
}

func maximizeXorAndXor(nums []int) int64 {
	n := len(nums)
	type pair struct{ and, xor, or int } // 多算一个子集 OR，用于剪枝
	subSum := make([]pair, 1<<n)
	subSum[0].and = -1
	for i, x := range nums {
		highBit := 1 << i
		for mask, p := range subSum[:highBit] {
			subSum[highBit|mask] = pair{p.and & x, p.xor ^ x, p.or | x}
		}
	}
	subSum[0].and = 0

	sz := bits.Len(uint(slices.Max(nums)))
	b := make(xorBasis, sz)
	maxXor2 := func(sub uint) (res int) {
		clear(b)
		xor := subSum[sub].xor
		for ; sub > 0; sub &= sub - 1 {
			x := nums[bits.TrailingZeros(sub)]
			b.insert(x &^ xor)
		}
		return xor + b.maxXor()*2
	}

	ans := 0
	u := 1<<n - 1
	for i, p := range subSum {
		j := u ^ i
		if p.and+subSum[j].or*2-subSum[j].xor > ans { // 有机会让 ans 变得更大
			ans = max(ans, p.and+maxXor2(uint(j)))
		}
	}
	return int64(ans)
}

func main() {
	nums := []int{2, 3}
	result := maximizeXorAndXor(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

class XorBasis:
    """线性基模板"""
    def __init__(self, size: int):
        self.b = [0] * size
    
    def insert(self, x: int):
        """向线性基中插入一个数"""
        while x > 0:
            # x 的最高位
            i = x.bit_length() - 1
            if i >= len(self.b):
                break
            if self.b[i] == 0:
                # x 和之前的基是线性无关的
                self.b[i] = x  # 新增一个基，最高位为 i
                return
            x ^= self.b[i]  # 保证参与 max_xor 的基的最高位互不相同
    
    def max_xor(self) -> int:
        """获取最大异或值"""
        res = 0
        # 从高到低贪心：越高的位，越必须是 1
        for i in range(len(self.b) - 1, -1, -1):
            res = max(res, res ^ self.b[i])
        return res
    
    def clear(self):
        """清空线性基"""
        for i in range(len(self.b)):
            self.b[i] = 0

def maximize_xor_and_xor(nums: List[int]) -> int:
    n = len(nums)
    # 计算子集的 and, xor, or 值
    sub_sum = [{"and": -1, "xor": 0, "or": 0} for _ in range(1 << n)]
    sub_sum[0]["and"] = -1
    
    for i, x in enumerate(nums):
        high_bit = 1 << i
        for mask in range(high_bit):
            idx = high_bit | mask
            p = sub_sum[mask]
            sub_sum[idx]["and"] = p["and"] & x
            sub_sum[idx]["xor"] = p["xor"] ^ x
            sub_sum[idx]["or"] = p["or"] | x
    
    sub_sum[0]["and"] = 0
    
    # 确定线性基大小
    max_val = max(nums)
    sz = max_val.bit_length()
    basis = XorBasis(sz)
    
    def max_xor2(sub: int) -> int:
        """计算子集 sub 的最大异或值"""
        basis.clear()
        xor_val = sub_sum[sub]["xor"]
        
        temp = sub
        while temp > 0:
            # 获取最低位的1的位置
            idx = (temp & -temp).bit_length() - 1
            x = nums[idx]
            # 对应 Go 中的 &^ 操作符（位清除）
            basis.insert(x & (~xor_val))
            temp &= temp - 1  # 清除最低位的1
        
        return xor_val + basis.max_xor() * 2
    
    ans = 0
    u = (1 << n) - 1
    
    for i, p in enumerate(sub_sum):
        j = u ^ i
        # 剪枝条件
        if p["and"] + sub_sum[j]["or"] * 2 - sub_sum[j]["xor"] > ans:
            ans = max(ans, p["and"] + max_xor2(j))
    
    return ans

def main():
    nums = [2, 3]
    result = maximize_xor_and_xor(nums)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>

using namespace std;

// 线性基模板
class XorBasis {
private:
    vector<int> b;

public:
    XorBasis(int size) : b(size, 0) {}

    void insert(int x) {
        while (x > 0) {
            // x 的最高位
            int i = 31 - __builtin_clz(x);  // __builtin_clz 计算前导0的个数
            if (b[i] == 0) {
                // x 和之前的基是线性无关的
                b[i] = x;  // 新增一个基，最高位为 i
                return;
            }
            x ^= b[i];  // 保证参与 maxXor 的基的最高位互不相同
        }
    }

    int maxXor() {
        int res = 0;
        // 从高到低贪心：越高的位，越必须是 1
        for (int i = b.size() - 1; i >= 0; i--) {
            res = max(res, res ^ b[i]);
        }
        return res;
    }

    void clear() {
        fill(b.begin(), b.end(), 0);
    }
};

long long maximizeXorAndXor(const vector<int>& nums) {
    int n = nums.size();

    // 结构体存储子集的 and, xor, or 值
    struct Subset {
        int and_val;
        int xor_val;
        int or_val;
    };

    vector<Subset> subSum(1 << n);
    subSum[0].and_val = -1;
    subSum[0].xor_val = 0;
    subSum[0].or_val = 0;

    // 预处理所有子集的值
    for (int i = 0; i < n; i++) {
        int highBit = 1 << i;
        int x = nums[i];
        for (int mask = 0; mask < highBit; mask++) {
            int idx = highBit | mask;
            subSum[idx].and_val = subSum[mask].and_val & x;
            subSum[idx].xor_val = subSum[mask].xor_val ^ x;
            subSum[idx].or_val = subSum[mask].or_val | x;
        }
    }
    subSum[0].and_val = 0;

    // 确定线性基大小
    int max_val = *max_element(nums.begin(), nums.end());
    int sz = max_val == 0 ? 1 : 32 - __builtin_clz(max_val);
    XorBasis basis(sz);

    // 计算子集的最大异或值
    auto maxXor2 = [&](unsigned int sub) -> int {
        basis.clear();
        int xor_val = subSum[sub].xor_val;

        unsigned int temp = sub;
        while (temp > 0) {
            // 获取最低位的1的位置
            int idx = __builtin_ctz(temp);  // 计算末尾0的个数
            int x = nums[idx];
            // Go 中的 &^ 操作符（位清除）等价于 x & (~xor_val)
            basis.insert(x & (~xor_val));
            temp &= temp - 1;  // 清除最低位的1
        }

        return xor_val + basis.maxXor() * 2;
    };

    int ans = 0;
    int u = (1 << n) - 1;

    for (int i = 0; i < (1 << n); i++) {
        int j = u ^ i;
        // 剪枝条件
        if (subSum[i].and_val + subSum[j].or_val * 2 - subSum[j].xor_val > ans) {
            ans = max(ans, subSum[i].and_val + maxXor2(j));
        }
    }

    return ans;
}

int main() {
    vector<int> nums = {2, 3};
    long long result = maximizeXorAndXor(nums);
    cout << result << endl;
    return 0;
}