豆包 快速 LeetCode 3287. 求出数组中最大序列值 C++实现
LeetCode 3287. 求出数组中最大序列值 C++ 完整实现
题意回顾
给定数组 nums 和整数 k ，选出长度为 2k 的子序列，拆分为前 k 个、后 k 个不重叠部分：
1. 前 k 个数全部按位或得到 A
2. 后 k 个数全部按位或得到 B
3. 求 A ^ B 的最大值
限制条件： nums[i] < 128 ，所有或运算结果值域仅 0~127 ，这是核心优化点。
核心思路
1. 前缀DP： pre[i][j][v] 表示前 i 个元素中选 j 个，按位或等于 v 是否可达
2. 后缀DP： suf[i][j][v] 表示下标 i 到末尾选 j 个，按位或等于 v 是否可达
3. 枚举分割点 split ：前 split 个取 k 个， split 之后取 k 个，两段无交集
4. 遍历所有合法 A、B ，计算异或并维护最大值
C++ 标准版代码（可直接提交LeetCode）AC
cpp
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxValue(vector<int>& nums, int k) {
const int MAX_VAL = 128;
int n = nums.size();
k = min(k, n / 2);
// pre[i][cnt][val]：前i个数选cnt个，或值val是否存在
vector<vector<vector<bool>>> pre(n + 1, vector<vector<bool>>(k + 1, vector<bool>(MAX_VAL, false)));
pre[0][0][0] = true;
for (int i = 1; i <= n; ++i) {
int x = nums[i - 1];
for (int cnt = 0; cnt <= k; ++cnt) {
// 不选当前数字，复制上一层状态
pre[i][cnt] = pre[i - 1][cnt];
// 选当前数字，从 cnt-1 转移
if (cnt > 0) {
for (int v = 0; v < MAX_VAL; ++v) {
if (pre[i - 1][cnt - 1][v]) {
pre[i][cnt][v | x] = true;
}
}
}
}
}
// suf[i][cnt][val]：下标i ~ n-1 选cnt个，或值val是否存在
vector<vector<vector<bool>>> suf(n + 1, vector<vector<bool>>(k + 1, vector<bool>(MAX_VAL, false)));
suf[n][0][0] = true;
for (int i = n - 1; i >= 0; --i) {
int x = nums[i];
for (int cnt = 0; cnt <= k; ++cnt) {
suf[i][cnt] = suf[i + 1][cnt];
if (cnt > 0) {
for (int v = 0; v < MAX_VAL; ++v) {
if (suf[i + 1][cnt - 1][v]) {
suf[i][cnt][v | x] = true;
}
}
}
}
}
int ans = 0;
// split 分割点：前split个取k，剩余取k
for (int split = k; split <= n - k; ++split) {
auto& left = pre[split][k];
auto& right = suf[split][k];
for (int a = 0; a < MAX_VAL; ++a) {
if (!left[a]) continue;
for (int b = 0; b < MAX_VAL; ++b) {
if (right[b]) {
ans = max(ans, a ^ b);
}
}
}
}
return ans;
}
};
空间优化版本（滚动数组，节省内存）
原始三维数组内存占用较高，用滚动数组压缩第一维：
cpp
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxValue(vector<int>& nums, int k) {
const int MAX_VAL = 128;
int n = nums.size();
k = min(k, n / 2);
// 前缀滚动DP
vector<vector<vector<bool>>> pre(n + 1, vector<vector<bool>>(k + 1, vector<bool>(MAX_VAL, false)));
vector<vector<bool>> dp(k + 1, vector<bool>(MAX_VAL, false));
dp[0][0] = true;
pre[0] = dp;
for (int i = 1; i <= n; ++i) {
int x = nums[i - 1];
auto cur = dp;
for (int cnt = 1; cnt <= k; ++cnt) {
for (int v = 0; v < MAX_VAL; ++v) {
if (dp[cnt - 1][v]) {
cur[cnt][v | x] = true;
}
}
}
dp.swap(cur);
pre[i] = dp;
}
// 后缀滚动DP
vector<vector<vector<bool>>> suf(n + 1, vector<vector<bool>>(k + 1, vector<bool>(MAX_VAL, false)));
fill(dp.begin(), dp.end(), vector<bool>(MAX_VAL, false));
dp[0][0] = true;
suf[n] = dp;
for (int i = n - 1; i >= 0; --i) {
int x = nums[i];
auto cur = dp;
for (int cnt = 1; cnt <= k; ++cnt) {
for (int v = 0; v < MAX_VAL; ++v) {
if (dp[cnt - 1][v]) {
cur[cnt][v | x] = true;
}
}
}
dp.swap(cur);
suf[i] = dp;
}
int ans = 0;
for (int split = k; split <= n - k; ++split) {
auto& left = pre[split][k];
auto& right = suf[split][k];
for (int a = 0; a < MAX_VAL; ++a) {
if (!left[a]) continue;
for (int b = 0; b < MAX_VAL; ++b) {
if (right[b]) {
ans = max(ans, a ^ b);
}
}
}
}
return ans;
}
};
复杂度说明
1. 时间复杂度：O(n \cdot k \cdot 128 + n \cdot 128^2)
- 前后缀DP：O(nk \cdot 128)
- 枚举分割点求最大异或：O(n \cdot 128^2)
2. 空间复杂度：标准版 O(nk \cdot 128)；滚动优化版内存减半
关键细节
1. MAX_VAL = 128 ：题目保证 nums[i] < 128 ，任意数字或运算结果不会超过127；
2. 分割点范围 [k, n-k] ：保证左右两边都能选出k个数字；
3. 状态转移：复制上一层表示不选当前数，循环或更新表示选当前数；
4. 最终遍历所有 a,b 组合求异或最大值。