Желтый QA

🧠 Возвращаемся с разбором задачи из прошлого поста. Ошибка была в инициализации: max_sum = 0 вместо первого элемента массива. Ноль здесь — не «нейтральное» значение, а неявное предположение, что ответ не может быть меньше нуля. Но по условию подмассив должен содержать хотя бы один элемент — а значит, если все числа отрицательные, правильный ответ тоже отрицательный. Функция же в таком случае вернёт 0 — сумму «пустого» подмассива, которого по условию не существует. Пример-ловушка:

nums = [-3, -1, -2] → вернёт 0 вместо -1 nums = [-5] → вернёт 0 вместо -5

Разберём nums = [-3, -1, -2] по шагам:

num = -3 → current = max(-3, 0 + (-3)) = -3 → max_sum = max(0, -3) = 0 num = -1 → current = max(-1, -3 + (-1)) = -1 → max_sum = max(0, -1) = 0 num = -2 → current = max(-2, -1 + (-2)) = -2 → max_sum = max(0, -2) = 0

Все реальные суммы отрицательные, но max_sum так и не опустился ниже стартового нуля — и функция возвращает ответ, который вообще не соответствует никакому подмассиву. Правильное решение:

def max_subarray(nums): max_sum = current = nums[0] # инициализируем первым элементом! for num in nums[1:]: current = max(num, current + num) max_sum = max(max_sum, current) return max_sum

Теперь стартовое значение — это сумма реального подмассива из одного элемента, и функция корректно работает в том числе на массивах из одних отрицательных чисел. Кстати, этот алгоритм — знаменитый алгоритм Кадане, а ошибка с инициализацией нулём — самый частый способ его «сломать». Такие задачи любят спрашивать на собеседованиях, поэтому хорошо помнить о том, как их решать ❤️ Подписывайтесь 📚 #задача