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

更多资讯

单列索引与多列索引：从典型查询看索引设计

RISC-V开发板实战：将Bao Hypervisor移植到RVA23的完整指南

RVA23开发板移植Bao hypervisor与FreeRTOS实战

智慧工厂安全应急管理系统：UWB定位与气体监控技术落地拆解

[特殊字符] Aider 小白安装教程（Windows / macOS / Linux）：用 TaoToken 统一 Key 打通配置

MCP 打通 InoProShop 与 Claude Code：PLC 编程自动化实践

今日更新

BunnyScholar硕士论文跨章节检查：长文档双栏如何梳理因果链

维普标红教育学SEM量表怎么办：助研君修改与RMSEA指标复核

知网标红有限元仿真与网格划分怎么办：助研君按字修改与参数复核

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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