先纠正原笔记的一处错配标题、链接和Java代码对应力扣152乘积最大子数组但原题面与大部分文字推导讲的是1567乘积为正数的最长子数组长度。它们不是同一道题。对于[1,-2,-3,4]最大乘积是24正乘积的最长长度是4。这篇现在只解152找出一个非空、连续的子数组返回它的最大乘积而不是长度。1. 只存最大乘积会漏掉什么先看[-2,3,-4]。走到3时以3结尾的连续子数组只有[3] 乘积 3 [-2,3] 乘积 -6如果只存最大值3接上-4只能看到3×(-4)-12。被丢掉的-6接上-4却得到24。这不是“负数一定不好”。一个很小的负乘积遇到下一个负数就可能成为很大的正乘积。所以以当前位置结尾的状态要同时记最大乘积和最小乘积。2. 状态的单位是乘积不是长度定义f[i]所有以位置i结尾的非空连续子数组中的最大乘积。g[i]同一组子数组中的最小乘积。处理当前数x时一个以这里结尾的子数组只有两种来源单独选择x或者把x接到前一位置结尾的某个子数组上。设上一位置最大值为oldMax最小值为oldMin那么候选是x 从当前位重新开始 oldMax × x 接在以前的最大乘积后 oldMin × x 接在以前的最小乘积后x为正时乘法保持大小关系x为负时大小关系翻转x为0时所有延长的乘积都变成0。无论哪一种最大和最小都能从这三个候选中取到newMax max(x, oldMax*x, oldMin*x) newMin min(x, oldMax*x, oldMin*x)为什么中间那些乘积不用保留因为它们乘同一个x之后仍落在两端产生的值之间不能产生新的最大或最小。与另一道题“正、负乘积的最长长度”不同这里不是遇到元素就给长度加1而是真的相乘。3. 原手写过程值得保留但数值要核对这张图对应的是最大乘积题反而比原文字题面更贴近代码。下面重算图中输入原图在数字3处把g写成6按“最小乘积”定义应为3完整结果以此表为准。当前x以当前位结尾的最大乘积f最小乘积g扫描至此的答案22223636-2-2-12644-486-5240-20240-8160-192024071120-134401120-9120960-10080120960例如走到-8不能延续“上一格最大值240最重要”的想法。这里最大值160来自(-20)×(-8)最小值-1920来自240×(-8)。而走到7时最小值-13440暂时很小下一位-9又让它翻成120960。这正是两个状态不断交换作用的过程。4. 初始化与返回值也要对上定义从第一个元素开始只有一个非空子数组所以最大、最小和答案都初始化为nums[0]。这比给辅助状态填1更直接原来的1是乘法单位元不是空子数组可以作为答案。不能把答案初始为0。输入[-2]时唯一非空子数组的乘积是-2不是0。也不能只返回最后一格最大值。对于[2,3,-2,4]最后一格最大值是4但全局答案是前面的6。[-2,0,-1]的答案为0因为零本身可以作为非空子数组。不能跨过零把-2与-1相乘得到2那两个元素不是连续子数组。5. Java实现先用数组保留原思路class Solution { public int maxProduct(int[] nums) { int n nums.length; int[] f new int[n]; int[] g new int[n]; f[0] g[0] nums[0]; int answer nums[0]; for (int i 1; i n; i) { int x nums[i]; int fromMax f[i - 1] * x; int fromMin g[i - 1] * x; f[i] Math.max(x, Math.max(fromMax, fromMin)); g[i] Math.min(x, Math.min(fromMax, fromMin)); answer Math.max(answer, f[i]); } return answer; } }时间O(n)两张表的额外空间O(n)。输入非空是题面前提。当前官方题面保证任何子数组乘积都在32位整数范围内所以此处使用int自行扩题时不能只保证最终答案不溢出还要处理最小状态和中间乘法的溢出。6. 压成两个变量时别提前覆盖旧值每一轮只依赖上一轮因而可以压空间class RollingSolution { public int maxProduct(int[] nums) { int maximum nums[0]; int minimum nums[0]; int answer nums[0]; for (int i 1; i nums.length; i) { int x nums[i]; int fromMax maximum * x; int fromMin minimum * x; maximum Math.max(x, Math.max(fromMax, fromMin)); minimum Math.min(x, Math.min(fromMax, fromMin)); answer Math.max(answer, maximum); } return answer; } }先把两个乘积算好再改maximum和minimum。否则更新minimum时使用新maximum相当于同一个x参与了两轮乘法。时间不变额外空间O(1)。7. 怎么验证这次没有又写成另一道题独立对照程序枚举每个连续子数组用long逐项相乘取最大值。它不使用最大/最小状态转移。同时运行备份中的原代码、二维状态整理版和滚动版核对它们都返回乘积而不是长度也检查输入数组没有被修改。测试包括题目样例、单负数、零分隔、连续负数、上面的原图输入再穷举{-2,-1,0,1,2}上长度1至6的所有数组并加入固定种子的随机输入。长度最多10、元素绝对值最多3的随机组保证乘积范围可控不拿题外溢出数据误判题内算法。另外故意只保留最大状态确认[-2,3,-4]能揭露错误故意先更新最大值再算最小值[-2,-2,-2]会错误返回16而不是4。两个错误不一定被同一个样例抓住反例本身也要运行核对。原图说明了状态怎么变化独立枚举负责核对实现而题面、状态单位、返回值一致是写题解的第一道检查。 
长河君 · 2026/10/6 7:27:08 · 阅读 1.2k 乘积最大子数组：为什么最大值旁边，还要存一个最小值？
先纠正原笔记的一处错配标题、链接和Java代码对应力扣152乘积最大子数组但原题面与大部分文字推导讲的是1567乘积为正数的最长子数组长度。它们不是同一道题。对于[1,-2,-3,4]最大乘积是24正乘积的最长长度是4。这篇现在只解152找出一个非空、连续的子数组返回它的最大乘积而不是长度。1. 只存最大乘积会漏掉什么先看[-2,3,-4]。走到3时以3结尾的连续子数组只有[3] 乘积 3 [-2,3] 乘积 -6如果只存最大值3接上-4只能看到3×(-4)-12。被丢掉的-6接上-4却得到24。这不是“负数一定不好”。一个很小的负乘积遇到下一个负数就可能成为很大的正乘积。所以以当前位置结尾的状态要同时记最大乘积和最小乘积。2. 状态的单位是乘积不是长度定义f[i]所有以位置i结尾的非空连续子数组中的最大乘积。g[i]同一组子数组中的最小乘积。处理当前数x时一个以这里结尾的子数组只有两种来源单独选择x或者把x接到前一位置结尾的某个子数组上。设上一位置最大值为oldMax最小值为oldMin那么候选是x 从当前位重新开始 oldMax × x 接在以前的最大乘积后 oldMin × x 接在以前的最小乘积后x为正时乘法保持大小关系x为负时大小关系翻转x为0时所有延长的乘积都变成0。无论哪一种最大和最小都能从这三个候选中取到newMax max(x, oldMax*x, oldMin*x) newMin min(x, oldMax*x, oldMin*x)为什么中间那些乘积不用保留因为它们乘同一个x之后仍落在两端产生的值之间不能产生新的最大或最小。与另一道题“正、负乘积的最长长度”不同这里不是遇到元素就给长度加1而是真的相乘。3. 原手写过程值得保留但数值要核对这张图对应的是最大乘积题反而比原文字题面更贴近代码。下面重算图中输入原图在数字3处把g写成6按“最小乘积”定义应为3完整结果以此表为准。当前x以当前位结尾的最大乘积f最小乘积g扫描至此的答案22223636-2-2-12644-486-5240-20240-8160-192024071120-134401120-9120960-10080120960例如走到-8不能延续“上一格最大值240最重要”的想法。这里最大值160来自(-20)×(-8)最小值-1920来自240×(-8)。而走到7时最小值-13440暂时很小下一位-9又让它翻成120960。这正是两个状态不断交换作用的过程。4. 初始化与返回值也要对上定义从第一个元素开始只有一个非空子数组所以最大、最小和答案都初始化为nums[0]。这比给辅助状态填1更直接原来的1是乘法单位元不是空子数组可以作为答案。不能把答案初始为0。输入[-2]时唯一非空子数组的乘积是-2不是0。也不能只返回最后一格最大值。对于[2,3,-2,4]最后一格最大值是4但全局答案是前面的6。[-2,0,-1]的答案为0因为零本身可以作为非空子数组。不能跨过零把-2与-1相乘得到2那两个元素不是连续子数组。5. Java实现先用数组保留原思路class Solution { public int maxProduct(int[] nums) { int n nums.length; int[] f new int[n]; int[] g new int[n]; f[0] g[0] nums[0]; int answer nums[0]; for (int i 1; i n; i) { int x nums[i]; int fromMax f[i - 1] * x; int fromMin g[i - 1] * x; f[i] Math.max(x, Math.max(fromMax, fromMin)); g[i] Math.min(x, Math.min(fromMax, fromMin)); answer Math.max(answer, f[i]); } return answer; } }时间O(n)两张表的额外空间O(n)。输入非空是题面前提。当前官方题面保证任何子数组乘积都在32位整数范围内所以此处使用int自行扩题时不能只保证最终答案不溢出还要处理最小状态和中间乘法的溢出。6. 压成两个变量时别提前覆盖旧值每一轮只依赖上一轮因而可以压空间class RollingSolution { public int maxProduct(int[] nums) { int maximum nums[0]; int minimum nums[0]; int answer nums[0]; for (int i 1; i nums.length; i) { int x nums[i]; int fromMax maximum * x; int fromMin minimum * x; maximum Math.max(x, Math.max(fromMax, fromMin)); minimum Math.min(x, Math.min(fromMax, fromMin)); answer Math.max(answer, maximum); } return answer; } }先把两个乘积算好再改maximum和minimum。否则更新minimum时使用新maximum相当于同一个x参与了两轮乘法。时间不变额外空间O(1)。7. 怎么验证这次没有又写成另一道题独立对照程序枚举每个连续子数组用long逐项相乘取最大值。它不使用最大/最小状态转移。同时运行备份中的原代码、二维状态整理版和滚动版核对它们都返回乘积而不是长度也检查输入数组没有被修改。测试包括题目样例、单负数、零分隔、连续负数、上面的原图输入再穷举{-2,-1,0,1,2}上长度1至6的所有数组并加入固定种子的随机输入。长度最多10、元素绝对值最多3的随机组保证乘积范围可控不拿题外溢出数据误判题内算法。另外故意只保留最大状态确认[-2,3,-4]能揭露错误故意先更新最大值再算最小值[-2,-2,-2]会错误返回16而不是4。两个错误不一定被同一个样例抓住反例本身也要运行核对。原图说明了状态怎么变化独立枚举负责核对实现而题面、状态单位、返回值一致是写题解的第一道检查。