Наибольшая возрастающая подпоследовательность
Самая длинная цепочка роста — элементы можно пропускать.
1function lisLength(a: number[]): number {2 const n = a.length3 const dp = a.map(() => 1) // dp[i] — длина LIS, кончающейся в i4 5 for (let i = 1; i < n; i++) {6 for (let j = 0; j < i; j++) {7 if (a[j] < a[i] && dp[j] + 1 > dp[i]) {8 dp[i] = dp[j] + 19 }10 }11 }12 13 return Math.max(...dp)14}Проблема
Самая длинная цепочка роста — элементы можно пропускать.
Что вы видите
Столбики с подписями len: каждый смотрит на всех меньших слева и продлевает лучшую цепочку.
Как это работает
dp[i] — длина LIS, кончающейся в i: перебираем j < i с a[j] < a[i] и продлеваем. O(n²) версия — фундамент; существует O(n log n) с бинарным поиском. Восстановление — по предкам.
Пошаговый разбор
- 01
Каждый элемент
len=1 как минимум.
- 02
Меньшие слева
Продлеваем лучшую цепочку.
- 03
Рекорд
Максимум по len.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
Переносы строк
Оптимальный auto-wrap через LIS.
Тренды
Поиск растущих цепочек в последовательностях.
Собеседования
Топ-3 задача по динамике.
Связанные алгоритмы
«Цепочка роста сквозь массив»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.