乘积最大子数组

描述

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

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

子数组 是数组的连续子序列。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

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

        int max_so_far = nums[0]; // 以当前元素为结尾的子数组的最大乘积
        int min_so_far = nums[0]; // 以当前元素为结尾的子数组的最小乘积
        int ans = nums[0]; // 记录最大乘积

        for(int i = 1; i < n; i++){
            int temp = max_so_far;
            max_so_far = max({nums[i], nums[i]*max_so_far, nums[i]*min_so_far}); // 更新以当前元素为结尾的子数组的最大乘积
            min_so_far = min({nums[i], nums[i]*temp, nums[i]*min_so_far}); // 更新以当前元素为结尾的子数组的最小乘积
            ans = max(ans, max_so_far); // 更新最大乘积
        }

        return ans;
    }
};

解题思路：

这是一道经典的动态规划问题。我们可以使用 dp 数组来记录以每个元素为结尾的子数组的最大乘积和最小乘积。因为乘积可能为负数，所以还需要记录最小乘积。

具体来说，我们使用 max_so_far 和 min_so_far 分别记录以当前元素为结尾的子数组的最大乘积和最小乘积。对于下一个元素 nums[i]，我们需要更新 max_so_far 和 min_so_far。由于乘积可能为负数，所以我们还需要记录上一个元素的 max_so_far，用于计算当前元素的最小乘积。

如果当前元素为正数，那么最大乘积为当前元素乘以以前一个元素为结尾的子数组的最大乘积；最小乘积为当前元素乘以以前一个元素为结尾的子数组的最小乘积。如果当前元素为负数，那么最大乘积为当前元素乘以以前一个元素为结尾的子数组的最小乘积；最小乘积为当前元素乘以以前一个元素为结尾的子数组的最大乘积。如果当前元素为 0，那么以当前元素为结尾的子数组的最大乘积和最小乘积都为 0。

最终，我们只需要返回所有以元素为结尾的子数组中的最大乘积即可。

C++代码

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

        int max_so_far = nums[0]; // 以当前元素为结尾的子数组的最大乘积
        int min_so_far = nums[0]; // 以当前元素为结尾的子数组的最小乘积
        int ans = nums[0]; // 记录最大乘积

        for(int i = 1; i < n; i++){
            int temp = max_so_far;
            max_so_far = max({nums[i], nums[i]*max_so_far, nums[i]*min_so_far}); // 更新以当前元素为结尾的子数组的最大乘积
            min_so_far = min({nums[i], nums[i]*temp, nums[i]*min_so_far}); // 更新以当前元素为结尾的子数组的最小乘积
            ans = max(ans, max_so_far); // 更新最大乘积
        }

        return ans;
    }
};