豆包 专家 LeetCode 3287. 求出数组中最大序列值 Java实现

题目正确题意给你一个整数数组 nums 和正整数 k 需要选出长度为 2*k 的子序列将其均分为前后各 k 个元素- 前半段所有元素做按位或得到值 A- 后半段所有元素做按位或得到值 B- 序列值 A XOR B求所有合法子序列中的最大序列值 。核心观察- 数值范围 1 nums[i] 2^7 128 因此任意个元素按位或的结果最多只有 128 种可能这是优化的关键。- 采用前后缀DP 枚举分割点的思路预处理前缀选j个的所有可能或值、后缀选j个的所有可能或值再枚举前后段的分割点遍历所有或值组合求异或最大值。Java 完整实现javapublic class Solution {public int maxValue(int[] nums, int k) {int n nums.length;final int MAX_VAL 1 7; // 数值小于128或结果最多128种// pre[i][j][v]前i个元素中选j个按位或结果为v是否可达boolean[][][] pre new boolean[n 1][k 1][MAX_VAL];pre[0][0][0] true;for (int i 1; i n; i) {int num nums[i - 1];for (int j 0; j k; j) {// 不选当前元素直接继承前i-1个的结果System.arraycopy(pre[i - 1][j], 0, pre[i][j], 0, MAX_VAL);// 选当前元素从j-1个的状态转移if (j 0) {for (int v 0; v MAX_VAL; v) {if (pre[i - 1][j - 1][v]) {pre[i][j][v | num] true;}}}}}// suf[i][j][v]从下标i到数组末尾选j个按位或结果为v是否可达boolean[][][] suf new boolean[n 1][k 1][MAX_VAL];suf[n][0][0] true;for (int i n - 1; i 0; i--) {int num nums[i];for (int j 0; j k; j) {// 不选当前元素继承后i1个的结果System.arraycopy(suf[i 1][j], 0, suf[i][j], 0, MAX_VAL);// 选当前元素从j-1个的状态转移if (j 0) {for (int v 0; v MAX_VAL; v) {if (suf[i 1][j - 1][v]) {suf[i][j][v | num] true;}}}}}int ans 0;// 枚举分割点前split个元素选k个后n-split个元素选k个for (int split k; split n - k; split) {boolean[] leftOr pre[split][k];boolean[] rightOr suf[split][k];// 遍历所有可能的或值组合求异或最大值for (int a 0; a MAX_VAL; a) {if (leftOr[a]) {for (int b 0; b MAX_VAL; b) {if (rightOr[b]) {ans Math.max(ans, a ^ b);}}}}}return ans;}}复杂度分析1. 时间复杂度O(n * k * 128 n * 128²)- 前后缀DP各 O(nk128)n最大400、k最大200、128是值域上限计算量极低。- 枚举分割点求最大值最多n个分割点每个点最多128*128次异或运算总开销可忽略。2. 空间复杂度O(n * k * 128)使用三维布尔数组存储可达状态。思路补充- 按位或的性质选的元素越多或结果不会变小且值域被限制在128以内因此用布尔数组标记可达结果比集合更高效。- 分割点的意义保证前半段和后半段的元素完全不重叠对应子序列的前后k个元素来自数组不同区间天然满足子序列的下标递增要求。需要我补充空间优化版的一维DP实现吗