Код переполнен целым числом только для 1 из 2 функциональных реализаций - PullRequest
Новая
       7

Код переполнен целым числом только для 1 из 2 функциональных реализаций

0 голосов
/ 06 мая 2019

Я решаю 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;
    }

1 Ответ

2 голосов
/ 06 мая 2019

Два блока кода не эквивалентны. 

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

тогда они будут эквивалентны.

...