乘积最大子数组

怎样从“nums=[2,3,-2,4]，求乘积最大子数组。”推导出 线性 DP · 双轨乘积，并证明每次状态变化都不会漏掉答案？

中心结论：每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

在本站主例中，nums=[2,3,-2,4]，求乘积最大子数组。

算法最终需要得到或观察：最大乘积 6，最优子数组 [2,3]。

1func maxProduct(nums []int) int {
2    curMax := nums[0]
3    curMin := nums[0]
4    ans := nums[0]
5
6    for i := 1; i < len(nums); i++ {
7        x := nums[i]
8        prevMax, prevMin := curMax, curMin
9        curMax = max3(x, prevMax*x, prevMin*x)
10        curMin = min3(x, prevMax*x, prevMin*x)
11        if curMax > ans {
12            ans = curMax
13        }
14    }
15
16    return ans
17}

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1func maxProduct(nums []int) int {
2    curMax := nums[0]
3    curMin := nums[0]
4    ans := nums[0]
5
6    for i := 1; i < len(nums); i++ {
7        x := nums[i]
8        prevMax, prevMin := curMax, curMin
9        curMax = max3(x, prevMax*x, prevMin*x)
10        curMin = min3(x, prevMax*x, prevMin*x)
11        if curMax > ans {
12            ans = curMax
13        }
14    }
15
16    return ans
17}

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 curMax（以 i 结尾最大）、curMin（以 i 结尾最小）、ans（全局最大乘积）。
3. 3转移每一步按照 每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。
4. 4收尾读取 最大乘积 6，最优子数组 [2,3]。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：curMax（以 i 结尾最大）、curMin（以 i 结尾最小）、ans（全局最大乘积）。

1func maxProduct(nums []int) int {
2    curMax := nums[0]
3    curMin := nums[0]
4    ans := nums[0]
5
6    for i := 1; i < len(nums); i++ {
7        x := nums[i]
8        prevMax, prevMin := curMax, curMin
9        curMax = max3(x, prevMax*x, prevMin*x)
10        curMin = min3(x, prevMax*x, prevMin*x)
11        if curMax > ans {
12            ans = curMax
13        }
14    }
15
16    return ans
17}

给出一个数组，要求找出这个数组中连续元素乘积最大的值。 这一题是 DP 的题，状态转移方程是：最大值是 `Max(f(n)) = Max( Max(f(n-1)) n, Min(f(n-1)) n)`；最小值是 `Min(f(n)) = Min( Max(f(n-1)) n, Min(f(n-1)) n)`。只要动态维护这两个值，如果最后一个数是负数，最大值就在负数 最小值中产生，如果最后一个数是正数，最大值就在正数 最大值中产生。

每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。

执行过程中持续维护：curMax（以 i 结尾最大）、curMin（以 i 结尾最小）、ans（全局最大乘积）。

正确性依赖以下不变量：curMax/curMin 是以 i 结尾的局部状态；ans 是全局答案，只增不减。；必须先保存 prevMax/prevMin，再更新 curMax/curMin，顺序不能乱。

面试时可以压缩为：这题和最大子数组和不同，乘积遇到负数会发生符号翻转，所以当前位置的最大乘积可能来自之前的最小乘积。遍历时维护以 i 结尾的最大乘积 curMax 和最小乘积 curMin，每一步从 x、prevMax×x、prevMin×x 三者中更新，再用 curMax 更新全局答案 ans。时间 O(n)，空间 O(1)。

落到当前题，执行机制可以压缩为：每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1func maxProduct(nums []int) int {
2    curMax := nums[0]
3    curMin := nums[0]
4    ans := nums[0]
5
6    for i := 1; i < len(nums); i++ {
7        x := nums[i]
8        prevMax, prevMin := curMax, curMin
9        curMax = max3(x, prevMax*x, prevMin*x)
10        curMin = min3(x, prevMax*x, prevMin*x)
11        if curMax > ans {
12            ans = curMax
13        }
14    }
15
16    return ans
17}

1. 1题目与输入nums=[2,3,-2,4]，求乘积最大子数组。 因为：每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。
2. 2Scene 2 · 反例：只维护 curMax 会失败负×负反杀：历史最小乘积乘负数可跃升为最大。 因为：若跳过 curMin，24 永远无法进入 ans。
3. 3Scene 3 · 核心状态：curMax / curMin / ans混淆 curMax 与 ans 是最常见的面试失误之一。 因为：ans 用 curMax 更新，但 curMax 本身每步重算。
4. 4Scene 5 · 初始化首元素初始化三条滚动状态。 因为：ans 初值必须是 nums[0]，不能是 0。
5. 5Scene 6 · i=1 · x=+3ans 刷新！用 curMax 更新全局最优（不是把 curMax 当最终答案）。 因为：ans 只增不减，记录历史最优的「以 i 结尾」最大乘积。
6. 6预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
7. 7Scene 8 · i=3 · x=+4三候选人竞争完毕，curMax/curMin 沿各自轨道延伸。 因为：每步 O(1) 更新，扫描一遍数组。
8. 8收尾与复杂度最大乘积 6，最优子数组 [2,3]。 因为：时间 O(n) · 空间 O(1)。每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。

1func maxProduct(nums []int) int {
2    curMax := nums[0]
3    curMin := nums[0]
4    ans := nums[0]
5
6    for i := 1; i < len(nums); i++ {
7        x := nums[i]
8        prevMax, prevMin := curMax, curMin
9        curMax = max3(x, prevMax*x, prevMin*x)
10        curMin = min3(x, prevMax*x, prevMin*x)
11        if curMax > ans {
12            ans = curMax
13        }
14    }
15
16    return ans
17}

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

1func maxProduct(nums []int) int {
2    curMax := nums[0]
3    curMin := nums[0]
4    ans := nums[0]
5
6    for i := 1; i < len(nums); i++ {
7        x := nums[i]
8        prevMax, prevMin := curMax, curMin
9        curMax = max3(x, prevMax*x, prevMin*x)
10        curMin = min3(x, prevMax*x, prevMin*x)
11        if curMax > ans {
12            ans = curMax
13        }
14    }
15
16    return ans
17}

func maxProduct(nums []int) int {
	minimum, maximum, res := nums[0], nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] < 0 {
			maximum, minimum = minimum, maximum
		}
		maximum = max(nums[i], maximum*nums[i])
		minimum = min(nums[i], minimum*nums[i])
		res = max(res, maximum)
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
    // 1. 主例
    //    输入：mode="max-product-subarray", nums=[2,3,-2,4]
    //    期望：最大乘积 6，最优子数组 [2,3]。
    //
    // 2. 失败 / 未命中
    //    检查：只维护 curMax：负×负时 prevMin×x 可反杀成最大，会漏掉最优解（如 [-2,3,-4] 漏 24）。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC53 最大和；LC713 乘积小于 K
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[2,3,-2,4]，求乘积最大子数组。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。
4. 4证明curMax/curMin 是以 i 结尾的局部状态；ans 是全局答案，只增不减。；必须先保存 prevMax/prevMin，再更新 curMax/curMin，顺序不能乱。
5. 5复杂度时间 O(n)，空间 O(1)