Алгоритмы с нуля
Наибольшая возрастающая подпоследовательность: ДП за O(n^2) и приём с массивом хвостов за O(n log n)
У тебя есть массив чисел и ты хочешь найти длину самой длинной цепочки которая продолжает расти — но числа не обязаны стоять рядом. Из [10, 9, 2, 5, 3, 7, 101, 18] ты можешь выбрать 2, 5, 7, 101 (или 2, 3, 7, 18): четыре числа, каждое больше предыдущего, разбросанные по массиву. Это подпоследовательность, не подряд идущий срез. Это задача о наибольшей возрастающей подпоследовательности (LIS). Естественное одномерное ДП решает её за O(n^2). Потом хитрый приём — держи крошечный массив “лучших хвостов” и бинарно ищи в нём — снижает стоимость до O(n log n). Подвох который сбивает всех с толку: этот массив хвостов даёт правильную длину, но сам по себе он не является корректной подпоследовательностью.
После этого урока ты можешь точно определить LIS: наибольшую строго возрастающую подпоследовательность массива, где элементы сохраняют относительный порядок, но не обязаны быть соседними. Ты можешь написать ДП за O(n^2) — dp[i] это длина наибольшей возрастающей подпоследовательности которая заканчивается на индексе i, вычисляемая как 1 + max(dp[j]) по всем j < i с nums[j] < nums[i], а ответ это max(dp). Ты можешь написать метод за O(n log n): держи массив tails где tails[k] это наименьшее возможное последнее значение возрастающей подпоследовательности длины k+1, и для каждого нового значения бинарно ищи первый хвост который >= x и перезаписывай его (или добавляй в конец). Ты понимаешь точно почему tails.length это длина LIS, тогда как сам tails не является настоящей подпоследовательностью. Ты можешь сформулировать обе сложности. Следующий урок продолжает арку ДП-на-последовательностях.
Что это наибольшая возрастающая подпоследовательность?
Подпоследовательность это то что ты получаешь удаляя ноль или больше элементов из массива без переупорядочивания остальных. Так [2, 7, 18] это подпоследовательность [10, 9, 2, 5, 3, 7, 101, 18], но [7, 2] нет (неправильный порядок). Наибольшая возрастающая подпоследовательность (LIS) это самая длинная такая подпоследовательность чьи значения строго возрастают (каждый элемент строго больше предыдущего).
nums = [10, 9, 2, 5, 3, 7, 101, 18]
one LIS = 2, 5, 7, 101 (length 4)
another = 2, 3, 7, 18 (length 4)Может быть несколько LIS одной длины; обычно нам нужна только длина. Заметь “подпоследовательность” (разбросанная, порядок сохранён) отличается от “подмассива/подстроки” (подряд). LIS не требует чтобы выбранные элементы были соседями.
Подход 1: одномерное ДП за O(n^2)
Определи состояние dp[i] = длина наибольшей возрастающей подпоследовательности которая заканчивается ровно на индексе i. Каждая возрастающая подпоследовательность где-то заканчивается, так ответ это max(dp) по всем i.
Как мы заполняем dp[i]? Подпоследовательность заканчивающаяся на i это некоторая более короткая подпоследовательность заканчивающаяся на более раннем индексе j < i с nums[j] < nums[i], плюс приделанный nums[i]. Чтобы сделать её как можно длиннее, выбери лучший такой j:
dp[i] = 1 + max( dp[j] ) over all j < i with nums[j] < nums[i]
dp[i] = 1 if no such j exists (nums[i] starts fresh)
answer = max(dp[0..n-1])Каждый элемент сам по себе это подпоследовательность длины 1, так мы инициализируем каждый dp[i] = 1. Два вложенных цикла (i внешний, j внутренний) дают O(n^2).
Подход 2: массив хвостов за O(n log n)
ДП за O(n^2) перепроверяет все более ранние индексы для каждого i. Более быстрый метод заменяет этот перебор бинарным поиском, держа один маленький массив, tails:
tails[k]= наименьшее возможное последнее значение любой возрастающей подпоследовательности длиныk + 1.
Почему “наименьшее возможное”? Потому что меньший хвост легче расширить позже — он оставляет больше места будущему элементу быть больше него. Хранение минимального хвоста на каждую длину жадно ровно в нужном смысле. Длина tails в конце это длина LIS.
Для каждого значения x в nums, делай одно из двух:
- Добавить в конец: если
xбольше каждого хвоста (большеtails[last]), он расширяет самую длинную цепочку на один, так добавь его. - Заменить: иначе, найди первый хвост который
>= xи перезапиши его наx. Это говорит “подпоследовательность той длины может теперь заканчиваться меньшим значениемx”, что может только помочь будущим расширениям. Поиск этой позиции это бинарный поиск (нижняя граница: первый индекс гдеtails[idx] >= x), потому чтоtailsвсегда отсортирован по возрастанию.
Это идея patience-сортировки (раскладывай карты на стопки, каждая стопка отсортирована; число стопок это длина LIS).
Смотри как эволюционирует tails
Прогони nums = [10, 9, 2, 5, 3, 7, 101, 18] через правило хвостов. Каждый шаг либо добавляет в конец (найдена новая самая длинная длина), либо заменяет первый хвост >= x:
x = 10 append tails = [10]
x = 9 replace tails[0] tails = [9]
x = 2 replace tails[0] tails = [2]
x = 5 append tails = [2, 5]
x = 3 replace tails[1] tails = [2, 3]
x = 7 append tails = [2, 3, 7]
x = 101 append tails = [2, 3, 7, 101]
x = 18 replace tails[3] tails = [2, 3, 7, 18]Итоговый tails = [2, 3, 7, 18], длина 4. Длина LIS равна 4. (Здесь итоговый tails оказался настоящей подпоследовательностью, но это везение — смотри Inset о том почему это не гарантировано.)
Почему tails всегда отсортирован? Подпоследовательности длины k могут заканчиваться значением как минимум таким же маленьким как у длины (k-1) плюс ещё один шаг вверх, так более длинным цепочкам нужны бо́льшие минимальные хвосты. Инвариант “tails строго возрастает” держится всё время, что ровно и позволяет нам бинарно искать в нём.
ДП за O(n^2) (ясное и прямое)
Состояние dp[i] = длина наибольшей возрастающей подпоследовательности заканчивающейся на i.
1
function lisN2(nums) {
2
if (nums.length === 0) return 0;
3
// dp[i] = length of LIS ending exactly at index i. Every element alone is length 1.
4
const dp = new Array(nums.length).fill(1);
5
6
for (let i = 1; i < nums.length; i++) {
7
for (let j = 0; j < i; j++) {
8
// Can we extend the subsequence ending at j by appending nums[i]?
9
if (nums[j] < nums[i]) {
10
dp[i] = Math.max(dp[i], dp[j] + 1);
11
}
12
}
13
}
14
// The LIS can end at any index, so take the best dp value.
15
return Math.max(...dp);
16
}
- L2 Пустой вход не имеет подпоследовательности: длина 0.
- L4 Инициализируй каждый dp[i] единицей — один элемент это возрастающая подпоследовательность длины 1.
- L6 Внешний цикл: вычисляй dp[i] для каждой позиции по очереди.
- L7 Внутренний цикл: перебери все более ранние индексы j как кандидатов в предшественники.
- L9 Только строго меньшее более раннее значение может стоять перед nums[i] в возрастающей цепочке.
- L10 Возьми лучшего предшественника: dp[i] = 1 + max(dp[j]) по валидным j.
- L15 Ответ это максимум dp[i] — LIS может заканчиваться где угодно.
Метод с массивом хвостов за O(n log n)
Держи tails, где tails[k] это наименьший хвост любой возрастающей подпоследовательности длины k+1. Для каждого x бинарно ищи первый хвост >= x (нижняя граница). Добавь в конец если такого нет, иначе перезапиши тот хвост.
1
function lengthOfLIS(nums) {
2
const tails = [];
3
4
for (const x of nums) {
5
// Binary search: find the first index where tails[idx] >= x (lower bound).
6
let lo = 0, hi = tails.length;
7
while (lo < hi) {
8
const mid = lo + Math.floor((hi - lo) / 2);
9
if (tails[mid] < x) {
10
lo = mid + 1; // tails[mid] too small - x belongs to the right
11
} else {
12
hi = mid; // tails[mid] >= x - candidate, but keep looking left
13
}
14
}
15
16
if (lo === tails.length) {
17
tails.push(x); // x beats every tail: a new longest length
18
} else {
19
tails[lo] = x; // overwrite the first tail >= x with the smaller x
20
}
21
}
22
23
return tails.length; // LENGTH is the LIS length (tails itself is NOT a subsequence)
24
}
- L2 tails растёт до длины LIS; tails[k] это наименьшее возможное последнее значение цепочки длины (k+1).
- L6 Бинарный поиск нижней границы по отсортированному массиву tails — это шаг за O(log n).
- L9 tails[mid] < x значит x должен идти дальше вправо: подвинь lo за mid.
- L11 tails[mid] >= x это кандидат на место замены: сожми hi до mid, никогда ниже ответа.
- L16 lo == tails.length значит ни один хвост не был >= x, так x расширяет самую длинную цепочку: добавь его.
- L19 Иначе перезапиши tails[lo] на x: та же длина, но теперь меньший хвост (легче расширить).
- L23 Верни только длину. Содержимое tails не гарантированно является настоящей подпоследовательностью.
Запусти оба и сравни
Оба метода должны согласоваться по длине. Метод хвостов делает это за O(n log n).
Массив из равных [7, 7, 7, 7, 7] возвращает 1: “строго возрастающая” отвергает равных соседей, так каждая 7 просто продолжает заменять tails[0] и длина никогда не вырастает дальше 1.
Смотри как массив хвостов заполняется для nums = [10, 9, 2, 5, 3, 7, 101, 18]. Каждый шаг это одно значение x: либо добавление в конец (теперь возможна более длинная цепочка), либо замена (первый хвост >= x, найденный бинарным поиском, становится меньшим x). Клетки показывают текущий tails.
1
for (const x of nums) {
2
// lower bound: first idx with tails[idx] >= x
3
if (lo === tails.length) tails.push(x); // append
4
else tails[lo] = x; // replace
5
}
| Метод | Время | Память |
|---|---|---|
| ДП за O(n^2) | O(n^2) — два вложенных цикла по массиву | O(n) — массив dp |
| Хвосты + бинарный поиск | O(n log n) — n значений, каждое поиск за O(log n) | O(n) — массив tails |
Почему ДП это O(n^2)
Внешний цикл запускается n раз; для каждого i внутренний цикл перебирает до i более ранних индексов. Это 1 + 2 + ... + (n-1) ≈ n^2 / 2 сравнений = O(n^2). Память это единственный массив dp длины n = O(n).
Почему метод хвостов это O(n log n)
Каждое из n значений запускает ровно один бинарный поиск по tails, а tails никогда не превышает длину n, так каждый поиск это O(log n). Добавление/замена это O(1). Итого: n × O(log n) = O(n log n). Память это массив tails, максимум n записей = O(n).
time space
O(n^2) DP O(n^2) O(n)
tails + bsearch O(n log n) O(n) <- this lesson's speedupКогда ускорение имеет значение? Для n = 100,000, n^2 это десять миллиардов операций; n log n это около 1.7 миллиона. Метод хвостов это стандартный ответ когда n большое. ДП за O(n^2) проще для рассуждений и его стоит писать первым если тебе также нужно восстановить саму подпоследовательность (методу хвостов для этого нужна дополнительная бухгалтерия).
Какова длина LIS массива [3, 1, 8, 2, 5]?
В ДП за O(n^2), что представляет dp[i]?
В массиве хвостов, что это tails[k]?
Для каждого значения x, метод хвостов бинарно ищет какую позицию?
Почему `tails.length` это длина LIS, хотя `tails` не обязательно является настоящей подпоследовательностью?
Какова длина LIS строго возрастающего массива [1, 2, 3, 4, 5]?
Частая ошибка
Массив хвостов это НЕ сама настоящая подпоследовательность. Его длина это длина LIS, но его содержимое может быть значениями которые никогда не появлялись вместе в одной возрастающей цепочке. Конкретное доказательство: nums = [2, 5, 3, 7, 11, 8, 10, 13, 6] заканчивается итоговым tails = [2, 3, 6, 8, 10, 13] (длина 6, что является правильной длиной LIS). Но [2, 3, 6, 8, 10, 13] не является подпоследовательностью nums: 6 это самый последний элемент nums, однако здесь он сидит в середине tails впереди 8, 10, 13. Последняя замена (6 перезаписывает 7) понизила хвост для длины которая уже была финализирована, испортив содержимое, но оставив длину правильной. Чтобы восстановить настоящую подпоследовательность ты должен хранить ссылки на предшественников отдельно; один массив хвостов даёт тебе только длину.
Почему это работает
Почему хранить наименьший хвост на каждую длину? Жадная интуиция: если две возрастающие подпоследовательности обе имеют длину k, та что заканчивается меньшим значением строго полезнее, потому что любой будущий элемент который может расширить ту с бо́льшим хвостом может также расширить ту с меньшим хвостом (и возможно больше). Так мы никогда ничего не теряем всегда запоминая минимальный хвост для каждой длины. Это инвариант который держит массив хвостов, и поэтому перезапись первого хвоста >= x меньшим x всегда безопасна.
Граничные случаи
Строго возрастающая против неубывающей. Этот урок вычисляет строго возрастающую LIS, так равные соседи не считаются: [7, 7, 7] имеет длину LIS 1. Если вместо этого ты хочешь наибольшую неубывающую подпоследовательность (допускающую равные значения), смени бинарный поиск с нижней границы (первый хвост >= x) на верхнюю границу (первый хвост > x). Это однострочное изменение переключает строгое на нестрогое. Их путаница это самая частая ошибка в LIS: всегда подтверждай что хочет задача.
Ещё практика
Рецепт для применения. (1) Сформулируй вариант: строго возрастающая или неубывающая? (2) Для первого корректного решения или когда ты должен восстановить саму настоящую подпоследовательность, напиши ДП за O(n^2): dp[i] = 1 + max(dp[j]) по j < i с nums[j] < nums[i], ответ max(dp). (3) Для большого n, переключись на метод хвостов: для каждого x, бинарный поиск нижней границы, потом добавь в конец или замени, и верни tails.length. (4) Помни оговорку: длина массива хвостов это ответ, но его содержимое не является гарантированной подпоследовательностью.
Объясни задачу LIS, ДП за O(n^2), метод хвостов за O(n log n), и почему tails.length это ответ хотя tails не является настоящей подпоследовательностью.
Наибольшая возрастающая подпоследовательность (LIS) это наибольшая строго возрастающая подпоследовательность массива — элементы сохраняют свой порядок, но не обязаны быть подряд.
ДП за O(n^2): dp[i] = длина LIS заканчивающейся на индексе i = 1 + max(dp[j]) по всем j < i с nums[j] < nums[i]; инициализируй каждый dp[i] = 1; ответ это max(dp). Время O(n^2), память O(n).
Метод хвостов за O(n log n): держи tails где tails[k] это наименьшее последнее значение любой возрастающей подпоследовательности длины k+1. Для каждого x, бинарно ищи первый хвост >= x (нижняя граница); добавь x в конец если каждый хвост меньше, иначе перезапиши тот хвост меньшим x. Ответ это tails.length. Время O(n log n), память O(n).
Ключевая оговорка: tails.length это длина LIS, но сам tails не является гарантированной подпоследовательностью — его значения могут происходить из разных цепочек (доказательство: [2, 5, 3, 7, 11, 8, 10, 13, 6] заканчивается хвостами [2, 3, 6, 8, 10, 13], длина 6 правильная, содержимое невозможно как одна цепочка). Чтобы восстановить настоящую подпоследовательность, отслеживай ссылки на предшественников отдельно.
Строгое против неубывающего: нижняя граница (первый хвост >= x) даёт строго возрастающее; переключись на верхнюю границу (первый хвост > x) для неубывающего варианта.