Максимальный подмассив алгоритмом Кадане
В каждой позиции выбирается продолжение участка или новый старт.
Что такое Максимальный подмассив алгоритмом Кадане?
В каждой позиции выбирается продолжение участка или новый старт.
Найдите непрерывный участок с наибольшей суммой.
Когда это использовать?
- Понимать алгоритмы и структуры данных.
- Наблюдать каждый шаг и проверять граничные случаи.
- Сравнивать время работы и память.
Пример кода
main.py
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))Ожидаемый результат
6Как это работает
Достаточно одного прохода: время O(n), память O(1).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.