知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 71 - 乘积最大子数组 ## 题目(LeetCode 152) 给定整数数组,找到乘积最大的连续子数组。 ## 解法:维护最大最小值 ```java class Solution { public int maxProduct(int[] nums) { int max = nums[0], min = nums[0], res = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] < 0) { int tmp = max; max = min; min = tmp; } max = Math.max(nums[i], max * nums[i]); min = Math.min(nums[i], min * nums[i]); res = Math.max(res, max); } return res; } } ``` > 💬 **Q:这里的 max 和 min 分别代表什么?整体的思路是怎么样子的?流程呢?** > > **`max` 和 `min` 的含义**: > > - **`max`**:以当前位置 `nums[i]` **结尾**的连续子数组的**最大乘积** > - **`min`**:以当前位置 `nums[i]` **结尾**的连续子数组的**最小乘积**(可能是很大的负数) > - **`res`**:全局最大乘积(最终答案) > > **为什么要同时维护 min?** > > 因为乘法有个特殊性:**一个很小的负数 × 一个负数 = 一个很大的正数**。所以当前的"最小值"可能在下一步变成"最大值"。 > > **整体思路**: > > 和 Kadane 算法(最大子数组和)一样,每到一个新位置做决策:**带上前面的还是从自己重新开始**。区别是乘法要同时跟踪最大和最小。 > > **完整流程(以 `[-2, 3, -4]` 为例)**: > > ``` > 初始:max = -2, min = -2, res = -2 > > i=1, nums[1]=3(正数,不交换) > max = Math.max(3, -2×3) = Math.max(3, -6) = 3 > min = Math.min(3, -2×3) = Math.min(3, -6) = -6 > res = Math.max(-2, 3) = 3 > 此时:max=3(子数组[3]),min=-6(子数组[-2,3]) > > i=2, nums[2]=-4(负数!交换 max 和 min) > 交换后:max = -6, min = 3 > max = Math.max(-4, -6×-4) = Math.max(-4, 24) = 24 ← 负负得正! > min = Math.min(-4, 3×-4) = Math.min(-4, -12) = -12 > res = Math.max(3, 24) = 24 > > 最终答案:24(子数组 [-2, 3, -4]) > ``` > > **为什么遇到负数要交换?** > > ``` > nums[i] < 0 时: > 原来的 max(正的大数)× 负数 → 变成很小的负数 → 应该给 min > 原来的 min(负的大数)× 负数 → 变成很大的正数 → 应该给 max > 所以先交换,再做 max/min 的更新,逻辑就统一了。 > ``` > > **每步的决策**: > > ``` > max = Math.max(nums[i], max * nums[i]) > ↑ 从自己开始 ↑ 带上前面的 > ``` > > 和 Kadane 一模一样的思路,只是多了一个 min 的维护。 ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 负数会让最大变最小,所以同时维护当前最大和最小乘积,遇到负数就交换。 ## 说明 乘积最大子数组问题的关键在于负数的存在(负负得正),因此需要同时维护最大值和最小值。当前解法已是最优(O(n) 时间,O(1) 空间),是 Kadane 算法在乘法场景下的变体。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入