豆包专家 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实现吗

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

相关推荐

Claude Opus 4.7深度解析：从对话助手到推理协作者的范式跃迁

MPC8240嵌入式SoC架构解析：PowerPC核心与高度集成外设的经典设计

MC68HC912BD32工作模式与内存映射：嵌入式开发的架构基石

更多资讯

Windows Server 2025 Canary版VMware安装全解：UEFI/HVCI/TPM深度适配

大模型预训练数据质量过滤实战：基于MindSpore的完整方案与避坑指南

openrig开放式多卡GPU机架搭建指南：结构、供电与散热全解析

Python垃圾识别分类系统实战：从源码复现到部署避坑指南

RAG问答准确度优化实战：从数据层到生成层的系统调优指南

String[]与List＜String＞深度对比：底层原理、性能差异与选型指南

今日更新

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？