题目

解法：动态规划

思路

维护以当前位置结尾的子数组的最大和最小乘积，通过动态规划处理负数符号翻转的情况。

由于负数的存在，当前的最大乘积可能在乘以负数后变成最小乘积，而最小乘积可能变成最大乘积。因此需要同时维护最大和最小两个状态。每一步我们考虑当前元素本身，或当前元素与之前最大/最小乘积的乘积，确保不会遗漏任何可能的子数组情况。这种动态规划方法保证了每个位置我们都掌握了最优解，最终答案就是所有位置最大乘积中的最大值。

• Step 1: 初始化 maxp、minp 和 ans 为第一个元素
• Step 2: 遍历数组，若当前元素为负数则交换 maxp 和 minp
• Step 3: 更新 maxp 为当前元素与 maxp*当前元素的较大值
• Step 4: 更新 minp 为当前元素与 minp*当前元素的较小值
• Step 5: 更新 ans 为当前 ans 与 maxp 的较大值

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是数组长度，只需一次遍历。
• 空间复杂度: $O(1)$，只使用了常数个额外变量。

代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxp = nums[0];
        int minp = nums[0];
        int ans = nums[0];

        for(int i = 1; i < nums.size(); i++){
            if(nums[i] < 0){
                swap(maxp, minp);
            }

            maxp = max(nums[i], maxp * nums[i]);
            minp = min(nums[i], minp * nums[i]);

            ans = max(ans, maxp);
        }

        return ans;
    }
};