.jpg)
1003 字
5 分钟
乘积最大子数组
.png)
题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
解题思路
- 双状态动态规划：
- 同时维护当前最大值和最小值（考虑负负得正）
- 最大值 = max(当前值, 前最大值×当前值, 前最小值×当前值)
- 最小值 = min(当前值, 前最大值×当前值, 前最小值×当前值)
- 全局结果更新：
- 每步更新全局最大乘积
- 滚动变量优化：
- 仅需保存前一状态的最大最小值
- 边界处理：
- 空数组返回0
- 单元素返回该元素
- 处理包含0和负数的场景
关键洞察
- 负负得正特性：
- 负数可能使最小乘积逆转为最大值
- 必须同时维护最大和最小值
- 状态转移依赖：
- 当前状态同时依赖前一状态的最大值和最小值
- 断点重置机制：
- 遇到0时乘积序列重置
- 负数不中断序列（可能后续负负得正）
- 子数组连续性：
- 乘积子数组必须是连续序列
- 与子序列问题本质不同
复杂度分析
| 类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 只需遍历数组一次 |
| 空间复杂度 | O(n)（基础版） | 需存储 maxDP 和 minDP 数组 |
| O(1)（优化版） | 用变量代替数组，仅存储前一个状态 |
代码实现
基础版本
function maxProduct(nums) {
const n = nums.length;
// 创建最大乘积和最小乘积数组 const maxDP = new Array(n).fill(0); const minDP = new Array(n).fill(0);
// 初始化第一个元素 maxDP[0] = minDP[0] = nums[0]; let max = nums[0]; // 全局最大值
for (let i = 1; i < n; i++) { // 计算三种可能值：当前值、当前值×前最大值、当前值×前最小值 const candidates = [ nums[i], maxDP[i - 1] * nums[i], minDP[i - 1] * nums[i] ];
// 更新当前最大和最小乘积 maxDP[i] = Math.max(...candidates); minDP[i] = Math.min(...candidates);
// 更新全局最大值 max = Math.max(max, maxDP[i]); } return max;》}DP空间优化，滚动数组版本
/** * @param {number[]} nums * @return {number} */var maxProduct = function (nums) { let maxF = nums[0], minF = nums[0], result = nums[0];
for (let i = 1; i < nums.length; i++) { const cur = nums[i]; const tempMax = Math.max(cur, maxF * cur, minF * cur); const tempMin = Math.min(cur, maxF * cur, minF * cur);
maxF = tempMax; minF = tempMin; result = Math.max(result, maxF); } return result;};变种：输出最大乘积子数组
JavaScript
const maxProductWithSubarray = (nums) => { if (nums.length === 0) return 0;
let maxProd = nums[0], minProd = nums[0]; let result = nums[0]; // 记录子数组起止位置 let start = 0, end = 0; let minStart = 0, maxStart = 0;
for (let i = 1; i < nums.length; i++) { const prevMax = maxProd, prevMin = minProd; const prevMaxStart = maxStart;
// 更新最大值及起点 if (nums[i] >= Math.max(prevMax * nums[i], prevMin * nums[i])) { maxProd = nums[i]; maxStart = i; } else if (prevMax * nums[i] >= prevMin * nums[i]) { maxProd = prevMax * nums[i]; } else { maxProd = prevMin * nums[i]; maxStart = minStart; }
// 更新最小值及起点 if (nums[i] <= Math.min(prevMax * nums[i], prevMin * nums[i])) { minProd = nums[i]; minStart = i; } else if (prevMax * nums[i] <= prevMin * nums[i]) { minProd = prevMax * nums[i]; } else { minProd = prevMin * nums[i]; }
// 更新全局结果 if (maxProd > result) { result = maxProd; start = maxStart; end = i; } }
return { product: result, subarray: nums.slice(start, end + 1) };};实际应用场景
- 信号处理：音频波形中查找最大能量区段`
- 金融分析：股票收益率连续乘积最大化（复利）`
- 图像识别：检测图像中最亮区域（像素值乘积）`
- 生物信息学：DNA序列中高表达基因片段识别`