对于 2 个功能实现中的 1 个，代码是整数溢出

Question

我正在解决https://leetcode.com/problems/maximum-product-subarray/submissions/

我有 2 个解决这个问题的方法，我相信它们是等价的。但是，我收到错误 Line 24: Char 52: runtime error: signed integer overflow: -944784000 * 4 cannot be represented in type 'int' (solution.cpp) 用于某些大输入的第一个代码，但我不用于第二个。我认为这两个代码之间没有任何功能差异，那么为什么第一个代码会溢出？

代码 1

int maxProduct(vector<int>& nums) {
    if(nums.empty()) return 0;

    auto n = nums.size();
    int min_num = nums[0];
    int max_num = nums[0];
    int curr_max = nums[0];
    for(int i = 1; i < n; i++)
    {
        if(nums[i] < 0) {
            max_num = std::max(nums[i], min_num*nums[i]);
            min_num = std::min(nums[i], max_num*nums[i]);
        }
        else
        {
            max_num = std::max(nums[i], max_num*nums[i]);
            min_num = std::min(nums[i], min_num*nums[i]);                
        }
        curr_max = std::max(curr_max, max_num);
    }

    return curr_max;
}

代码 2

    int maxProduct(vector<int>& nums) {
        if(nums.empty()) return 0;

        auto n = nums.size();
        int min_num = nums[0];
        int max_num = nums[0];
        int curr_max = nums[0];
        for(int i = 1; i < n; i++)
        {
            if(nums[i] < 0) std::swap(max_num,min_num);

            max_num = std::max(nums[i], max_num*nums[i]);
            min_num = std::min(nums[i], min_num*nums[i]); 

            curr_max = std::max(curr_max, max_num);               
        }

        return curr_max;
    }

Answer 1

两段代码不等价。

if(nums[i] < 0) {
    max_num = std::max(nums[i], min_num*nums[i]);
    min_num = std::min(nums[i], max_num*nums[i]); // This uses modified max_num.
}

我相当确定这是一个错误。如果你把它改成

if(nums[i] < 0) {
    auto temp = std::max(nums[i], min_num*nums[i]);
    min_num = std::min(nums[i], max_num*nums[i]);  // This uses unmodified max_num
    max_num = temp;
}

那么它们就等价了。

对于 2 个功能实现中的 1 个，代码是整数溢出

Code is integer overflowing for only 1 of 2 functionally implementations

c++

overflow

integer-overflow

代码 1

代码 2