[力扣c++实现] 152. 乘积最大子数组

152. 乘积最大子数组

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;
    }
};