题目：
给你一个整数数组 nums 和一个 正 整数 k 。定义长度为 2 * x 的序列 seq 的 值 为：
(seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1]).
请你求出 nums 中所有长度为 2 * k 的 子序列 的 最大值 。
示例 1：
输入：nums = [2,6,7], k = 1
输出：5
解释：子序列 [2, 7] 的值最大，为 2 XOR 7 = 5 。
示例 2：
输入：nums = [4,2,5,6,7], k = 2
输出：2
解释：子序列 [4, 5, 6, 7] 的值最大，为 (4 OR 5) XOR (6 OR 7) = 2 。
提示：
2 <= nums.length <= 4001 <= nums[i] < 271 <= k <= nums.length / 2
暴力模拟
思路：
通过回溯法求解所有长度为 2k 的子序列，然后求最大值就行
代码：
class Solution {
public:
vector<int> path;
int ans;
int getValue() {
int k = path.size() / 2;
int pre = 0, last = 0;
for (int i = 0; i < 2 * k; i++) {
if (i < k) pre |= path[i];
else last |= path[i];
}
return pre ^ last;
}
void backTrack(vector<int>& nums, int start, int k) {
if (path.size() == 2 * k) {
ans = max(ans, getValue());
return;
}
if (start >= nums.size()) return;
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]);
backTrack(nums, i + 1, k);
path.pop_back();
backTrack(nums, i + 1, k);
}
return;
}
int maxValue(vector<int>& nums, int k) {
ans = 0;
backTrack(nums, 0, k);
return ans;
}
};
动态规划
思路：
长度为 2k 的序列的值的计算方式为，先将其拆成长度相同的前后子串，然后分别计算各子串的所有元素的按位或的结果，再将两个按位或的结果进行按位异或。为了求出 nums 的长度为 2k 的子序列的最大值，可以将 nums 分成左右两半，分别求出每一半中，长度为 k 的子序列的按位或的所有可能性，再两两求异或的最大值。这样的分法一共有 n−2k+1 种，其中 n 为数组 nums 的长度。并且我们可以用动态规划的方法来求出长度为 k 的子序列的按位或的结果的所有可能性。
记 dp[i][j] 为哈希集合，表示 nums[0...i] 中长度为 j 的自序列按位或的所有可能性。j≤k，且当 j 为 0 时，dp[i][j] 为空集。又根据题目限制，nums 元素的值为 0 到 127，因此 dp[i][j] 最多包含 128 个元素。进行转移时，dp[i][j] 首先会包含 dp[i−1][j] 的所有元素，表示不选取 nums[i]。还可以将 dp[i−1][j−1] 中的所有元素与 nums[i] 进行按位或，将结果添加进 dp[i][j]，表示选取nums[i]。我们可以将上述步骤抽象成一个函数，并进一步降低空间复杂度，只返回值 j=k 时的 dp值，可以算出左一半的长度为 k 的子序列的按位或的所有可能性。再将 nums 进行逆序后再次应用这个函数，即可计算出右一半的的长度为 k 的子序列的按位或的所有可能性。再两两求异或的最大值返回。
代码：
class Solution {
public:
int maxValue(vector<int>& nums, int k) {
auto findORs = [&](const vector<int>& nums, int k) -> vector<unordered_set<int>> {
vector<unordered_set<int>> dp;
vector<unordered_set<int>> prev(k + 1);
prev[0].insert(0);
for (int i = 0; i < nums.size(); ++i) {
for (int j = min(k - 1, i + 1); j >= 0; --j) {
for (int x : prev[j]) {
prev[j + 1].insert(x | nums[i]);
}
}
dp.push_back(prev[k]);
}
return dp;
};
vector<unordered_set<int>> A = findORs(nums, k);
vector<unordered_set<int>> B = findORs(vector<int>(nums.rbegin(), nums.rend()), k);
int mx = 0;
for (size_t i = k - 1; i < nums.size() - k; ++i) {
for (int a : A[i]) {
for (int b : B[nums.size() - i - 2]) {
mx = max(mx, a ^ b);
}
}
}
return mx;
}
};