hot100 乘积最大子数组(152)-北京尧图网络

本题采用动态规划与正负极值双重追踪算法又称负数符号翻转状态机解决一维数组中连续子数组最大乘积的求解问题。其核心本质是将“连续子数组和”如 Kadane 算法推演至乘法域通过同时维护以当前节点结尾的最大乘积与最小乘积完美破解了“负负得正”带来的非单调性拓扑突变。当前提供的源码利用滚动变量实现了时间复杂度 O(N) 和额外空间复杂度 O(1) 条件下的全局最优求解最终走向是精准输出连续子数组的最大乘积值。一、问题本质与数据模型拆解1.1 加法单调性 vs 乘法符号翻转在 LeetCode 53最大子数组和中由于加法满足基本的单调性正数使和变大负数使和变小我们只需要记录以当前元素结尾的最大和fMax[i]。如果fMax[i-1] 0则直接丢弃前缀从当前元素重新开始。然而在乘法域中加法的单调性质完全失效问题面临三大拓扑突变因素正数效应乘以一个正数大值更大小值更小。负数效应符号翻转乘以一个负数原先的“极大值”会瞬间变成“极小值”负数最大绝对值而原先的“极小值”负数最大绝对值则会反转翻盘瞬间暴涨为“极大值”。零值效应状态隔离与重置乘以 0 会导致此前积累的所有乘积收益瞬间归零强制将后续子数组的搜索起点重置到下一个元素。数组序列: [ 2, 3, -2, 4 ] │ 负数乘法触发状态翻转 │ 正数累乘: 2 ── 6 ── -12 ── -48 (若仅追踪最大值将彻底迷失方向) 实际极值: [2] [2,3] [-2] [4] └─ 最终全局最大值为 6 (子数组 [2,3])1.2 正负极值双重追踪拓扑模型为了应对负数带来的符号翻转算法在遍历到第i个元素x nums[i]时必须在内存中同时维持两个状态fMax[i]以nums[i]结尾的连续子数组的最大乘积。fMin[i]以nums[i]结尾的连续子数组的最小乘积通常为绝对值最大的负数作为潜在的反弹储备。对于当前元素x其参与构成的子数组乘积只可能有三种可能来源延续前缀最大值fMax[i-1] * x延续前缀最小值fMin[i-1] * x彻底截断前缀以当前元素x自身作为新子数组的起点x通过在这三种可能性中同时取Math.max与Math.min算法在数学上完全覆盖了x 0、x 0以及x 0的所有分支场景无需编写繁琐的if-else分支判断。二、算法演进脉络与多重解法综合对比在解决连续子数组最大乘积问题时算法从暴力枚举逐步演进到一维动态规划再进一步压缩至 O(1) 空间的滚动变量法。下表对比了各种解法的时空开销与工程特征解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷暴力三重/双重循环O(N^2)O(1)枚举所有可能的子数组起点与终点 [i, j]双重循环累乘更新全局最大值存在严重的数据重复计算在 N 2 * 10^4 时执行次数达 2 * 10^8 级别必然超时前后向双向扫描法 (Prefix/Suffix Scan)O(N)O(1)分别从左向右、从右向左累乘遇 0 重新置为 1利用偶数个负数必定全选的几何性质逻辑依赖奇偶负数分布特征缺乏通用 DP 状态机的扩展性难以直接记录子数组区间一维动态规划数组 (DP Table)O(N)O(N)开辟fMax[N]与fMin[N]两个 DP 数组完整保留每个位置的极值状态产生额外 O(N) 的堆内存分配开销降低 CPU L1 Data Cache 的缓存利用率滚动变量动态规划 (当前解法)O(N)O(1)发现当前状态仅依赖上一时刻状态利用temp临时变量原地压缩空间至三个标量达到理论时空复杂度下界代码精简且无任何 GC 压力三、核心逻辑分支与数学归纳法证明3.1 状态转移方程推导设nums数组长度为 N状态定义如下fMax代表以当前处理元素结尾的最大连续子数组乘积。fMin代表以当前处理元素结尾的最小连续子数组乘积。当遍历到新元素x时新的极值状态转移方程为$$fMax_{new} \max(\max(fMax_{old} \times x, fMin_{old} \times x), x)$$$$fMin_{new} \min(\min(fMin_{old} \times x, fMax_{old} \times x), x)$$方程正确性的完备性证明当 $x 0$ 时$fMax_{old} \times x$ 保持为候选极大值。$fMin_{old} \times x$ 保持为候选极小值。与 $x$ 自身比较可以处理 $fMax_{old} 1$即前缀乘积小于 1 导致拖累当前元素的情况。当 $x 0$ 时若 $fMin_{old}$ 为负数则 $fMin_{old} \times x$ 将翻转变为正数成为新的候选极大值。若 $fMax_{old}$ 为正数则 $fMax_{old} \times x$ 将翻转变为负数成为新的候选极小值。方程中的 $\max(\dots)$ 和 $\min(\dots)$ 自动完成了这种由符号翻转引起的“极值互换”逻辑。当 $x 0$ 时$fMax_{old} \times 0 0$$fMin_{old} \times 0 0$。结果均坍缩为 $0$强制将当前位置的极值重置为 0为下一轮循环提供了归零起点。3.2 状态污染State Pollution防护与temp变量原理在代码实现中存在一个极易引发 Bug 的状态依赖问题int temp fMax; fMax Math.max(Math.max(fMax * x, fMin * x), x); fMin Math.min(Math.min(fMin * x, temp * x), x);状态污染风险在更新fMin时方程需要使用上一时刻的旧最大值fMax_old。然而在上一行代码中fMax已经被覆写为了当前时刻的新最大值fMax_new。临时中转机制必须在更新fMax前利用局部变量temp将旧的fMax隐式拷贝一份。在计算fMin时传入temp * x从而斩断了状态覆写引发的数据污染保证了状态转移在时间逻辑上的原子性。3.3 初始值设定ans Integer.MIN_VALUE / 2与边界安全源码中将全局结果ans初始设定为Integer.MIN_VALUE / 2除以 2 是为了彻底防止在极端场景或后续扩展计算中触发 32 位有符号整型下溢Underflow。初始时将滚动变量fMax与fMin初始化为1乘法单位元确保数组第一个元素x介入时1 * x x可以正确启动状态机。四、算法执行状态机步进推演与图解4.1 示例 1 全量逐元素状态演进表输入nums [2, 3, -2, 4]状态机演进推演表步骤元素 x临时变量 temp (旧 fMax)计算 fMax_new计算 fMin_new刷新全局 ans当前状态说明初始--11Integer.MIN_VALUE / 2准备启动状态机121max(max(12, 12), 2) 2min(min(12, 12), 2) 2max(MIN, 2) 2首个元素输入极值均为 2232max(max(23, 23), 3) 6min(min(23, 23), 3) 3max(2, 6) 6连续正数累乘fMax 升至 63-26max(max(6*-2, 3*-2), -2) -2min(min(3*-2, 6*-2), -2) -12max(6, -2) 6触发负数翻转旧 fMin(3)*-2-6 成为新 fMax 候选44-2max(max(-24, -124), 4) 4min(min(-124, -24), 4) -48max(6, 4) 6负数拖累当前截断以 4 重新开始最终输出ans6。4.2 经典复杂用例零值隔断与连续负数交织推演输入nums [-2, 3, -4, 0, -2, -5, -1]索引位置: 0 1 2 3 4 5 6 数值 nums: -2 3 -4 0 -2 -5 -1 |---| |---------| | |-------------| 拓扑分段: 段 1 段 2 (正数) 零点段 3 (双负反弹)步进推演表步骤 i元素 xtemp (旧 fMax)fMaxfMin全局 ans关键事件与物理拓扑0-21-2-2-2初始负数fMax 与 fMin 同步为 -213-23-63正数融入截断负前缀fMax 重置为 32-4324-1224负负得正旧 fMin(-6) * -4 24刷新全局最大值30240024零点归零强行将 fMax 和 fMin 坍缩为 04-20-2-224穿越零点后的新起点5-5-210-524再次负负得正-2 * -5 106-1105-1024奇数个负数拉低当前值全局 ans 保持为 24最终输出ans24(对应子数组[-2, 3, -4])。五、 Java 源码实现与逐行硬核注释class Solution { /** * 求解数组中乘积最大的非空连续子数组的乘积 * * param nums 输入整数数组 * return 最大连续乘积值 */ public int maxProduct(int[] nums) { // 1. 全局最大值初始化使用极小值防护下溢确保能被数组中任意实际数值正确覆盖 int ans Integer.MIN_VALUE / 2; // 2. 状态机滚动变量定义 // fMax: 维持以当前元素结尾的最大连续子数组乘积 // fMin: 维持以当前元素结尾的最小连续子数组乘积作为负负得正的潜伏储备 // 均初始化为乘法单位元 1 int fMax 1; int fMin 1; // 3. 线性单向遍历数组驱动状态机往前推进 for (int x : nums) { // 核心防污染保护在 fMax 被更新前将上一时刻的旧 fMax 暂存入 temp int temp fMax; // 状态转移方程 1更新当前时刻的最大乘积 // 三者比对旧最大值*x、旧最小值*x、当前元素x自身 fMax Math.max(Math.max(fMax * x, fMin * x), x); // 状态转移方程 2更新当前时刻的最小乘积 // 必须使用 temp即旧 fMax规避数据已被上一行覆写的污染 Bug fMin Math.min(Math.min(fMin * x, temp * x), x); // 动态刷新全局最大乘积候选值 ans Math.max(fMax, ans); } // 4. 返回收敛得到的全局最大连续子数组乘积 return ans; } }六、复杂度分析与 JVM 硬件级优化视角6.1 复杂度分析时间复杂度O(N)算法仅包含一个单重for-each循环遍历长度为 N 的输入数组。循环体内部仅包含两次Math.max、两次Math.min、三次基础乘法与一次临时变量赋值。所有原子操作均为 O(1) 常数时间。总时间复杂度为严格的线性关系T(N) O(N)。空间复杂度O(1)算法仅开辟了ans、fMax、fMin、temp以及循环变量x等有限个基本数据类型int的栈内存变量。空间开销完全不随输入数组规模 N 的增长而增长额外空间复杂度为S(N) O(1)完全避免了堆内存分配与垃圾回收GC开销。6.2 CPU 分支预测Branch Prediction与CMOV无分支优化在高性能计算领域条件分支如if-else往往是 CPU 效率的“隐形杀手”。若分支预测失败会导致 CPU 流水线清空带来 10 到 20 个时钟周期的停顿惩罚。源码中采用了Math.max和Math.min嵌套的形式JavafMax Math.max(Math.max(fMax * x, fMin * x), x);HotSpot JVM 的 C2 即时编译器JIT Compiler在将此段字节码编译为 x86-64 机器码时会自动将Math.max优化为无分支的条件移动指令Conditional Move Instructions如cmovg或cmovl代码段; 示意汇编代码无分支极值比较 imul eax, ecx ; eax fMax * x imul ebx, ecx ; ebx fMin * x cmp eax, ebx ; 比较两乘积 cmovl eax, ebx ; 如果 eax ebx无条件分支将 ebx 赋给 eax cmp eax, ecx ; 再与 x (ecx) 进行比较 cmovl eax, ecx ; 锁定最大值这种无分支指令的编译模式彻底消除了分支预测失败的可能性使 CPU 流水线能够以极高的指令级并行度ILP满载运行。6.3 标量替换Scalar Replacement与寄存器分配由于fMax、fMin、temp均为局部基本类型变量且没有发生任何对象逃逸EscapeJVM 的逃逸分析Escape Analysis机制与 C2 编译器会直接对这些变量执行标量替换。在最终执行的机器码中这些变量不会在栈帧内存中开辟读写空间而是直接映射并保存在 CPU 的通用寄存器如%eax,%ebx,%ecx中。所有的乘法与极值比对操作均在 CPU 内部的高速寄存器之间瞬间完成内存访问次数降至零缓存命中率达到 100%。七、工业级工程应用延伸与变体拓扑扩展连续子数组最大乘积模型不仅是算法面试的高频考点其背后的“滚动状态机”与“极值追踪”思想在实际工业生产中有着广泛的应用。7.1 扩展变体还原最大乘积子数组的物理区间在实际工程业务中我们往往不仅需要获取“最大乘积数值”还需要获取“究竟是哪一段连续子数组创造了该最大值”。改进方案区间双指针追踪法由于负数翻转会导致最大值与最小值发生互换当发生互换时最大值子数组的起始边界实际上继承自上一时刻最小值的起始边界。因此我们需要同步维护四个索引指针maxStart,maxEnd: 当前最大值子数组的物理区间。minStart,minEnd: 当前最小值子数组的物理区间。public class SubarrayProductTracker { public static int[] findMaxProductSubarray(int[] nums) { int globalMax nums[0]; int fMax nums[0], fMin nums[0]; int curMaxStart 0, curMinStart 0; int bestStart 0, bestEnd 0; for (int i 1; i nums.length; i) { int x nums[i]; // 候选值 1: 继承旧 fMax * x int p1 fMax * x; // 候选值 2: 继承旧 fMin * x int p2 fMin * x; // 暂存旧状态与旧起始点 int prevMax fMax; int prevMin fMin; int prevMaxStart curMaxStart; int prevMinStart curMinStart; // 更新 fMax 及对应的起始索引 if (p1 p2 p1 x) { fMax p1; // curMaxStart 保持 prevMaxStart 不变 } else if (p2 p1 p2 x) { fMax p2; curMaxStart prevMinStart; // 继承旧 fMin 的起点 } else { fMax x; curMaxStart i; // 截断前缀自立门户 } // 更新 fMin 及对应的起始索引 if (p1 p2 p1 x) { fMin p1; curMinStart prevMaxStart; // 继承旧 fMax 的起点 } else if (p2 p1 p2 x) { fMin p2; // curMinStart 保持 prevMinStart 不变 } else { fMin x; curMinStart i; } // 刷新全局最优解物理区间 if (fMax globalMax) { globalMax fMax; bestStart curMaxStart; bestEnd i; } } return new int[]{bestStart, bestEnd, globalMax}; } }7.2 工业应用量化金融策略中的连续收益率波动风险控制在量化金融高频交易系统中资产的日收益率Return Rate或杠杆倍数变化往往表现为连续乘法关系$$Cumulative\_Return \prod_{ki}^{j} (1 r_k)$$最大回撤与最大连续杠杆收益评估风险控制引擎需要实时监控一段交易周期内连续时间窗口的最大收益乘积与最大下行风险最小乘积。流式状态机应用在处理 Kafka 实时注入的 Tick 级金融数据流时基于本题的滚动变量状态机算法能够以纯内存 $O(1)$ 空间、$O(1)$ 单次更新延迟的方式实时计算窗口内的极限波动率因子避免了存储海量历史 Tick 数据的硬件开销。八、全文总结与工程实战避坑指南8.1 算法实战避坑指南遗忘temp状态隔离直接写fMax ...; fMin Math.min(..., fMax * x)导致fMin误用了已更新的fMax这是初学者最常犯的逻辑溃败。初始化盲目设定为 0如果将fMax和fMin初始赋值为 0当数组全为负数如[-2, -3, -4]时0 会作为污染因子参与Math.max比较导致输出结果错误地变为 0正确答案应为 -2 或 24。整型乘法溢出Integer Overflow题目保证了子数组乘积在 32 位整型范围内但在实际业务中如浮点数或大整数乘积连续乘法极易突破上限。工程实现中应视情况切换为long型或Double.isInfinite()安全校验。8.2 核心要点终极复盘物理本质一维连续序列的乘法极值求解受负数翻转与零点截断双重制约。核心工具双状态滚动变量fMax与fMin分别锁定正向最大收益与负向最大反弹潜能。状态方程通过Math.max(Math.max(fMax * x, fMin * x), x)实现无分支的三方归一化决策。复杂度优势时间复杂度 O(N) 单向线性扫描空间复杂度 O(1) 通用寄存器级高效映射是状态压缩动态规划范畴内的经典范式。

hot100 乘积最大子数组(152)

相关推荐

C++高效解析GML：从XML处理到地理空间数据应用实践

【RAG】自主RAG案例讲解 - 基于GPT-4o和向量数据库

Agent Skills 实战第二课：先别写规格，用 /grill-with-docs 把需求问到底

更多资讯

最小二乘法在时间序列预测中的实战应用

最小二乘法在时间序列预测中的实践与应用

AISOP与传统SOP的智能进化：制造业效率与质量的双重革命

透明化学术引用系统：区块链与AI驱动的文献管理解决方案

电动汽车电池充放电Simulink仿真模型设计与CC-CV策略实现

动态规划解决爬楼梯最小花费问题

今日更新

多智能体协作系统架构设计与实践优化

大模型系统性入门实战指南：从原理到部署微调的全链路路线

鸿蒙文件系统沙箱机制解析与开发实践

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

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