豆包专家 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工作模式与内存映射：嵌入式开发的架构基石

更多资讯

基于深度学习的智能坐姿检测系统：Python+PyTorch实战

微机原理与接口技术 · 第4章《汇编语言及其程序设计》知识点

开源油藏模拟器OPM/Flow实战：安装部署与Eclipse差异化对比

CSS动效核心机制与高频效果实战解析

YOLOv8猴子检测权重训练：从数据集标注到模型部署全流程

Cursor Opus极速模式值不值？TaoToken统一API通道实测与配置避坑指南

今日更新

企业AI转型实战指南：从场景选择到落地避坑的完整路线图

OpenRig：本地大模型服务编排的轻量级运行时框架

夸克网盘1TB免费扩容领取全攻略：新老用户实操流程与避坑指南

本周精选

如何彻底离线使用 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 成本测算与选型避坑（附配置）

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