企业官网建设流程全解析

题目：

给你一个整数数组nums，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个32-位整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

题解：

这道题我在做的时候，觉的秒了，结果提交错了，才发现有一个很傻的问题，自己忽略了。

一、问题难点分析

与“最大子数组和”不同，本题的核心难点在于：

1 乘积会受到负数影响

• 两个负数相乘会变成正数

• 一个负数可能会让当前最大乘积瞬间变成最小值

• 一个当前的最小乘积，遇到负数反而可能成为最大值

最大值和最小值是相互转化的（这就是我第一遍没意识到的问题）

2 0 会“切断”子数组

• 一旦遇到 0，之前的连续乘积就失效

• 需要从当前位置重新开始计算

二、为什么不能只维护一个最大值？

如果只记录“当前最大乘积”：

• 当遇到负数时：

  • 原本很小的负数乘积 × 负数 → 可能变成最大正数

• 但如果你没有保存“最小乘积”，这个机会就丢了

因此：

必须同时维护「当前最大乘积」和「当前最小乘积」

三、动态规划思想

状态定义

设：

• maxProd[i]：以nums[i]结尾的子数组的最大乘积

• minProd[i]：以nums[i]结尾的子数组的最小乘积

但由于只依赖前一状态，可以进行状态压缩。

状态转移方程

当遍历到nums[i]时：

curMax = max( nums[i], prevMax * nums[i], prevMin * nums[i] ) curMin = min( nums[i], prevMax * nums[i], prevMin * nums[i] )

解释：

• nums[i]：从当前元素重新开始

• prevMax * nums[i]：延续之前的最大乘积

• prevMin * nums[i]：负负得正的可能性

四、算法流程

1. 初始化：

   • maxProd = nums[0]

   • minProd = nums[0]

   • ans = nums[0]

2. 从第二个元素开始遍历数组：

   • 先保存上一轮的maxProd和minProd

   • 根据状态转移方程更新当前最大、最小乘积

   • 用ans记录全局最大值

3. 遍历结束，返回ans

class Solution { public: int maxProduct(vector<int>& nums) { int curMax = nums[0]; int curMin = nums[0]; int ans = nums[0]; for (int i = 1; i < nums.size(); i++) { int x = nums[i]; int prevMax = curMax; int prevMin = curMin; curMax = max({x, prevMax * x, prevMin * x}); curMin = min({x, prevMax * x, prevMin * x}); ans = max(ans, curMax); } return ans; } };