leetcode 链接：乘积最大子数组

题目

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

示例：

  1. 输入: [2,3,-2,4]
  2. 输出: 6
  3. 解释: 子数组 [2,3] 有最大乘积 6。
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解答 & 代码

注意：可能出现数组中有两个负数，负负得正的情况，因此，使用动态规划时还需要考虑负数的情况（并且希望负的更多，最后积才会更大）

动态规划：设置数组 dpMax[] 和数组 dpMin[]，dpMax[i] 表示以第 i 个元素结尾的子数组的最大乘积，dpMin[i] 表示以第 i 个元素结尾的子数组的最小乘积
状态转移方程：

  • dpMax[i] = max{dpMax[i-1]×nums[i], dpMin[i-1]×nums[i], nums[i]}
  • dpMin[i] = min{dpMax[i-1]×nums[i], dpMin[i-1]×nums[i], nums[i]}

滚动数组：因为第 i 个状态之和第 i-1 个状态有关，因此无需数组缓存，根据滚动数组的思想，只需用两个变量 preMin 和 preMax 分别代表以前一个元素为结尾的子数组的最小乘积和最大乘积

时间复杂度 O(N)，空间复杂度 O(1)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        if(len < 1)
            return 0;

        int maxProd = nums[0];        // 乘积最大子数组的乘积
        int preMin = nums[0];        // 以前一个元素为结尾的子数组的最小乘积
        int preMax = nums[0];        // 以前一个元素为结尾的子数组的最大乘积
        for(int i = 1; i < len; ++i)
        {
            // 动态规划状态转移，计算以当前元素为结尾的子数组的最大乘积和最小乘积
            int curMax = max(preMax * nums[i], max(preMin * nums[i], nums[i]));
            int curMin = min(preMax * nums[i], min(preMin * nums[i], nums[i]));
            // 更新成绩最大子数组的乘积
            maxProd = max(maxProd, curMax);
            // 更新 preMin 和 preMax
            preMin = curMin;
            preMax = curMax;
        }

        return maxProd;
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 87.16% 的用户
内存消耗：11.4 MB, 在所有 C++ 提交中击败了 65.36% 的用户