Алгоритм Кадане
Максимальная сумма подотрезка за один проход: текущая сумма либо растёт, либо сбрасывается.
1function kadane(arr: number[]): number {2 let best = -Infinity3 let current = 04 5 for (const x of arr) {6 current = Math.max(x, current + x)7 best = Math.max(best, current)8 }9 10 return best11}Проблема
Найти непрерывный подотрезок с максимальной суммой (массив с отрицательными). Перебор всех подотрезков — O(n²). Кадане замечает: отрицательный «хвост» тащить незачем.
Что вы видите
Рамка «текущий» — растущий подотрезок; подпись best — рекорд. Отрицательная сумма сбрасывает рамку на текущий элемент; каждый новый рекорд фиксируется.
Как это работает
Инвариант: current — максимум сумм подотрезков, заканчивающихся в i. Переход: current = max(x, current + x) — либо продолжаем лучший из них, либо начинаем заново с x. Ответ — максимум current по всем i. Это простейшая динамика по подотрезкам.
Пошаговый разбор
- 01
Проход
Смотрим на очередной элемент x.
- 02
Расти или сброс
current = max(x, current + x).
- 03
Рекорд
best = max(best, current).
- 04
Один проход
O(n), памяти O(1).
Complexity и ограничения
Массив с отрицательными. Пустой подотрезок запрещён (иначе ответ ≥ 0 всегда).
Edge cases
- Все отрицательные
Ответ — максимум один элемент.
- Нули
Нули не мешают; best не ухудшается.
- Два максимума
Вернётся первый достигнутый.
Где встречается в реальности
Финансы
Максимальная просадка/рост котировок — зеркальный Кадане.
Обработка сигналов
Поиск самого «энергичного» участка сигнала.
Собеседования
Топ-1 задача на динамику по подотрезкам.
Связанные алгоритмы
«Лучший подотрезок за один проход — как?»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.