博客

152. 乘积最大子数组

给你一个整数数组 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-位 整数

1.c++

class Solution {
public:
    void interleaveCanChoose(std::set<int>& curVec,const int curNum,const std::set<int>& lastVec)
    {
        for (auto val : lastVec)
        {
            curVec.insert(curNum*val);
        }
    }

    int maxProduct(std::vector<int>& nums) {
        int size = (int)nums.size();
        if (size < 1)
            return 0;
        if (size == 1)
            return nums[0];
        if (size == 2)
            return std::max(nums[0]*nums[1],*std::max_element(nums.begin(),nums.end()));

        std::map<int,std::set<int>> multiValues;//sequence : canChooseValues:vector<int>
        multiValues[size - 1].insert(nums[size-1]);

        for (int i = size -2;i >= 0;--i)
        {
            multiValues[i].insert(nums[i]);
            interleaveCanChoose(multiValues[i],nums[i],multiValues[i+1]);
        }
        
        int maxNum = INT32_MIN;
        for (auto [pos,nums] : multiValues)
        {
            for (auto val : nums)
            {
                if (maxNum < val)
                    maxNum = val;
            }
        }
        return maxNum;
    }
};