豆包 快速 LeetCode 3287. 求出数组中最大序列值 C++实现

LeetCode 3287. 求出数组中最大序列值 C 完整实现题意回顾给定数组 nums 和整数 k 选出长度为 2k 的子序列拆分为前 k 个、后 k 个不重叠部分1. 前 k 个数全部按位或得到 A2. 后 k 个数全部按位或得到 B3. 求 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 标准版代码可直接提交LeetCodeACcpp#include vector#include algorithmusing namespace std;class Solution {public:int maxValue(vectorint nums, int k) {const int MAX_VAL 128;int n nums.size();k min(k, n / 2);// pre[i][cnt][val]前i个数选cnt个或值val是否存在vectorvectorvectorbool pre(n 1, vectorvectorbool(k 1, vectorbool(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是否存在vectorvectorvectorbool suf(n 1, vectorvectorbool(k 1, vectorbool(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剩余取kfor (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 algorithmusing namespace std;class Solution {public:int maxValue(vectorint nums, int k) {const int MAX_VAL 128;int n nums.size();k min(k, n / 2);// 前缀滚动DPvectorvectorvectorbool pre(n 1, vectorvectorbool(k 1, vectorbool(MAX_VAL, false)));vectorvectorbool dp(k 1, vectorbool(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;}// 后缀滚动DPvectorvectorvectorbool suf(n 1, vectorvectorbool(k 1, vectorbool(MAX_VAL, false)));fill(dp.begin(), dp.end(), vectorbool(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)- 前后缀DPO(nk \cdot 128)- 枚举分割点求最大异或O(n \cdot 128^2)2. 空间复杂度标准版 O(nk \cdot 128)滚动优化版内存减半关键细节1. MAX_VAL 128 题目保证 nums[i] 128 任意数字或运算结果不会超过1272. 分割点范围 [k, n-k] 保证左右两边都能选出k个数字3. 状态转移复制上一层表示不选当前数循环或更新表示选当前数4. 最终遍历所有 a,b 组合求异或最大值。