Особый случай в максимальном подмассиве - PullRequest
Новая
       27

Особый случай в максимальном подмассиве

0 голосов
/ 27 февраля 2019

Я использую разделяй и властвуй, чтобы решить проблему максимального подмассива.Он работает нормально в большинстве случаев, но не работает в особых случаях.Я думаю, что проблема может произойти здесь: 

struct subarray maximum_crossing(int A[], int low, int mid ,int high){
    int left_sum = INT_MIN;
    int left_max = mid;
    int sum = 0;
    for (int i=mid; i >= low; i--){
        sum += A[i];
        if (sum > left_sum){
            left_sum = sum;
            left_max = i;
        };
    };
    ..........
    ..........

Я проверяю это, и это действительно хорошо работает в общем случае.Но когда массив выглядит примерно так: {-2147483648, -2147483648, -2147483648}, он вернет максимальный подмассив, который начинается с 0 и заканчивается на 1, а максимальная сумма равна 0. Я думаю, это потому, что INT_MIN + INT_MIN будет0 в C.

Или в {-2147483648, -1, 0} код обнаружит, что максимальный подмассив начинается с 0 и заканчивается на 1, максимальная сумма равна 2147483648. Из-за этой проблемы, как толькомассив имеет -2147483648 и другое отрицательное значение, код не будет работать.

Я пытаюсь использовать оператор if, чтобы сначала проверить значение A [i], но я обнаружил, что это не лучшее решение.Потому что другое отрицательное значение все еще может складываться, чтобы превысить -2147483648Так есть ли более подходящий способ решить этот случай?

1 Ответ

0 голосов
/ 27 февраля 2019

максимальная сумма равна 2147483648

2147483648 (десятичное число) равно 2 ^ 31, если ваши int имеют 32-битное переполнение 2147483648 для подписанного int, поэтому max_sum не может быть 2147483648

использовать long (предположим на 64b) для sum и left_sum

...