Представьте дни вашего «финансового дневника»: в какие-то дни вы заработали (плюс), в какие-то потратили (минус). Вопрос: какая непрерывная полоса дней принесла максимальный суммарный доход?
Вы идёте по дням и в каждый момент решаете простую вещь: «если моя текущая полоса ушла в минус, она только тянет меня вниз — лучше забыть про неё и начать новую полосу с сегодняшнего дня». А лучший результат за всё время вы записываете отдельно, чтобы не потерять. Это и есть алгоритмЧёткая последовательность шагов для решения задачи за конечное число действий. Кадане.
Условие
Дан списокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. чисел (могут быть отрицательные). Найти максимальную сумму непрерывного подсписка (хотя бы из одного элемента).
Идём по списку и в каждой точке решаем: продолжить текущий подсписок или начать заново с текущего числа. Берём то, что даёт больше. Параллельно запоминаем лучший результат.
▶ kadane.py
Две переменные — два смысла
best — «рекорд»: лучшая сумма, которую мы вообще встречали. Меняется только в большую сторону.
current — сумма «полосы», которую мы тянем прямо сейчас.
current = max(x, current + x) — главное решение: либо продолжить полосу (current + x), либо начать новую с текущего числа (x). Берём вариант побольше.
best = max(best, current) — после каждого шага обновляем рекорд, если текущая полоса его побила.
Начинаем с nums[0] в обеих переменных и идём по nums[1:] — то есть со второго элемента.
💡Совет
Ключ к пониманию: current = max(x, current + x). Если накопленная сумма стала отрицательной, она только мешает — выгоднее «обнулиться» и начать с текущего числа. Это и есть суть динамического программирования: оптимальное решение строится из решений на префиксах.
💡Совет
🔮 Предскажите вывод
Какой будет ответ для списка [2, -1, 3, -10, 4]? Пройдитесь мысленно: где самая «доходная» непрерывная полоса? Запишите свою догадку, потом запустите.
▶ predict-kadane.py
Ответ — 4. Полоса [2, -1, 3] даёт 4, потом -10 уводит сумму глубоко в минус, и алгоритм «начинает заново» с 4. Лучшее значение так и осталось 4 (его дают как [2,-1,3], так и одиночная [4]).
⚠️ Частые ошибки новичков
Распространённая ошибка — инициализировать best = 0. Тогда на списке из одних отрицательных чисел алгоритм вернёт 0, хотя должен вернуть наибольшее (наименее отрицательное) число. Запустите сломанный код и почините: начинайте best и current с nums[0].
▶ broken-kadane.py
Заданиесредняярешение.py
Реализуйте max_subarray(nums) алгоритмом Кадане за O(n). Верните максимальную сумму непрерывного подсписка.
Заданиесредняярешение.py
Дополнительное упражнение. Напишите max_profit_window(prices), которая по списку дневных изменений цены возвращает максимальную сумму непрерывной полосы, но не меньше нуля (если все дни убыточны — вернуть 0, ведь можно «ничего не покупать»). Подсказка: это Кадане, но с нижней границей 0.
❓Проверь себя
Что означает выражение current = max(x, current + x)?
Почему best и current инициализируют значением nums[0], а не нулём?
Какая сложность у алгоритма Кадане?
ℹ️Важно
✅ Что вы узнали
Алгоритм Кадане находит максимальную сумму непрерывного подсписка за один проход O(n).
Идея: «отрицательный накопленный хвост только мешает — начни заново».
Важно разделять current (текущая полоса) и best (рекорд).
Инициализация значением nums[0] корректно работает с отрицательными числами.
Комментарии
Загрузка…
Загрузка комментариев…