[力扣c++实现]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-位 整数

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

    int maxProduct(std::vector& 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>multiValues;//sequence : canChooseValues:vectormultiValues[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;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧