Поиск максимальной суммы последовательных элементов массива. Алгоритм Кадане (динамическое программирование)

Сегодня мы узнаем об одном из простых, на первый взгляд, но далеко не самом очевидном алгоритме поиска максимальной суммы последовательных элементов в массиве. Этот алгоритм динамического программирования носит название алгоритм Кадане. Но сперва надо кое-что упомянуть о динамическом программировании.

Что такое динамическое программирование? 

Само слово динамическое подразумевает какое-либо движение, однако это не значит, что вы должны совершать танец с бубном, когда используете методы динамического программирования :-). Суть его заключается в следующем: оно позволяет разбивать сложную задачу на более простые подзадачи, которые решаются лишь раз, а эти решения хранятся в структурах данных (массивах, таблицах и т. д.). Иначе говоря, вам не нужно заниматься сложными вычислениями всякий раз, когда возникает похожая подпроблема, нужно лишь посмотреть на результаты предыдущих вычислений и совершить над ними необходимые операции. Данный метод решения задач в программировании позволяет намного ускорить процесс вычислений по сравнению с наивным подходом.

Что ж, приступим к изучению нашего главного гостя - алгоритма Кадане. Его применение в основном связано с поиском максимальной суммы последовательных элементов массива или в английском варианте - Maximum Subarray Problem.

Наивный подход заключается в подсчете суммы всех подмассивов данного массива. Этот q брут форс q крайне неэффективен при решении данной проблемы. Если наш массив имеет длину n, то сложность вычислений будет составлять O(n^2). Выглядит не очень хорошо, да?

И здесь приходит на помощь алгоритм Кадане. Вместо того, чтобы заново вычислять сумму подмассива, мы будем сравнивать текущий элемент и сумму предыдущих с добавлением текущего элемента. Так мы вычислим нашу локальную сумму или локальный максимум. Если наша локальная сумма (local_sum) окажется больше, то она станет новой максимальной суммой последовательных элементов массива (global_sum). В противном случае наша глобальная сумма не изменится. Именно здесь происходит вся магия алгоритма. Мы сохраняем предыдущее значение локального максимума и таким образом нам не нужно пересчитывать сумму всех предыдущих элементов заново. Благодаря такому подходу нам нужно пройти массив лишь один раз, чтобы найти максимальную сумму. Иллюстрация ниже показывает процесс нахождения локального максимума. 

И напоследок реализация данного алгоритма на языках Python:

и C#: