Отправлено: 26.07.22 22:01. Заголовок: №4848 (27.93) ошибка в решении

Здравствуйте.

В решении Д. Муфаззалова (27-93 mufazzalov.py) есть ошибка в логике. Дело в том, что current_min вычисляется с запозданием на один шаг, поэтому получается 2 варианта проблем.

Первый вариант, это когда минимальный хвост подсчитывается неверно и берется предпоследнее минимальное значение:

Данные

 
 5 3 
 -3 
 -1 
 -3 
 -3 
 -3 
 

Ответ будет - 10, а правильный -9. Проблема в том, что минимум для первого отрезка {-3, -1} вычислится как -3, а не -4, ведь current_min отстает на шаг и если нужный шаг стоит рядом с магическим числом, то алгоритм просто не успевает проверить последний вариант current_sub_sum.

Второй вариант проблем заключается в том, что по дефолту для current_min задается значение 0 для каждой новой итерации и если магические числа будут стоять рядом, то из-за того, что current_min запаздывает на шаг, в current_min не будет попадать начало отрезка с магическим числом и значение current_min так и будет оставаться равным нулю. Тогда для данных

 
 5 3 
 -10 
 -3 
 -3 
 -3 
 -3 
 

ответ будет -12, а правильный -9. Происходит это потому, что current_min из-за отставания на шаг не успевает обновиться и вместо 3 магических чисел на отрезке у нас получается 4 магических числа - хвост, который каждый раз должен содержать магическое число, это магическое число не содержит, потому что не успевает обновиться.

 Отправлено: 13.08.22 18:46. Заголовок: ап..

ап

 Отправлено: 17.08.22 19:03. Заголовок: Спасибо, автор обнов..

Спасибо, автор обновил свое решение.