kz-maxx

RU KZ
← Главная

Наибольшая возрастающая подпоследовательность

LIS: динамическое программирование O(n²), восстановление ответа и оптимизация O(n log n)

Что такое LIS?

LIS — это Longest Increasing Subsequence. По-русски: наибольшая возрастающая подпоследовательность.

Нам дан массив чисел. Нужно выбрать из него несколько элементов так, чтобы:

  • порядок элементов сохранился
  • выбранные числа строго возрастали
  • длина была максимальной
Подпоследовательность — это не обязательно подряд. Главное — не менять порядок элементов.

Пример

Дан массив: 

5 1 6 2 3 4

Одна из наибольших возрастающих подпоследовательностей: 

1 2 3 4

Ее длина: 

4

Почему нельзя взять 1 2 3 4 6? Потому что 6 стоит раньше, чем 2 3 4. Порядок менять нельзя.

Подпоследовательность и подотрезок

Термин Что значит Пример
Подпоследовательность можно пропускать элементы 1 2 4 из 5 1 6 2 3 4
Подотрезок элементы идут подряд 2 3 4 из 5 1 6 2 3 4
LIS — это именно подпоследовательность, а не подотрезок.

Главная идея DP

Придумаем массив: 

dp[i]

dp[i] — длина наибольшей возрастающей подпоследовательности, которая заканчивается именно в позиции i.

dp[i] = лучший ответ
если последний выбранный элемент — a[i]

Как сделать переход?

Чтобы посчитать dp[i], смотрим все предыдущие позиции j.

Если: 

a[j] < a[i]

значит можно поставить a[i] после a[j].

Тогда: 

dp[i] = max(dp[i], dp[j] + 1);

Базовое значение

Каждый элемент сам по себе уже является возрастающей подпоследовательностью длины 1. 

dp[i] = 1;

Поэтому сначала для всех i ставим: 

for (int i = 1; i <= n; i++) {
    dp[i] = 1;
}

Формула DP

dp[i] = 1;

for (int j = 1; j < i; j++) {
    if (a[j] < a[i]) {
        dp[i] = max(dp[i], dp[j] + 1);
    }
}

Ответ — максимум среди всех dp[i]. 

ans = max(ans, dp[i]);

Пример руками

Массив: 

5 1 6 2 3 4
i a[i] Лучшая подпоследовательность dp[i]
1 5 5 1
2 1 1 1
3 6 5 6 2
4 2 1 2 2
5 3 1 2 3 3
6 4 1 2 3 4 4

Задача 1: найти длину LIS

Дан массив из n чисел. Нужно найти длину наибольшей возрастающей подпоследовательности.

Input

6
5 1 6 2 3 4

Output

4

Полная реализация O(n²)

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;

int n;
int a[N];
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;

        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        ans = max(ans, dp[i]);
    }

    cout << ans;

    return 0;
}

Почему это O(n²)?

У нас два цикла: 

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
        ...
    }
}

Для каждой позиции i мы смотрим все предыдущие позиции j.

примерно n × n проверок
значит время O(n²)
Если n примерно до 5000, O(n²) часто проходит. Если n = 100000, нужно O(n log n).

Восстановление самой подпоследовательности

Иногда нужно вывести не только длину, но и саму LIS.

Для этого будем хранить: 

parent[i]

parent[i] — предыдущая позиция перед i в лучшей подпоследовательности.

если dp[i] улучшилось через j
значит parent[i] = j

Как обновлять parent?

if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
    dp[i] = dp[j] + 1;
    parent[i] = j;
}

После этого надо найти позицию pos, где dp[pos] максимальный. 

if (dp[i] > ans) {
    ans = dp[i];
    pos = i;
}

Как восстановить ответ?

Идем назад по массиву parent. 

vector<int> lis;

while (pos != -1) {
    lis.push_back(a[pos]);
    pos = parent[pos];
}

reverse(lis.begin(), lis.end());

Сначала получаем ответ с конца, поэтому в конце делаем reverse.

Полная реализация с восстановлением

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;

int n;
int a[N];
int dp[N];
int parent[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int ans = 0;
    int pos = -1;

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        parent[i] = -1;

        for (int j = 1; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }

        if (dp[i] > ans) {
            ans = dp[i];
            pos = i;
        }
    }

    vector<int> lis;

    while (pos != -1) {
        lis.push_back(a[pos]);
        pos = parent[pos];
    }

    reverse(lis.begin(), lis.end());

    cout << ans << '\n';

    for (int x : lis) {
        cout << x << ' ';
    }

    return 0;
}

Оптимизация O(n log n)

Если n большое, O(n²) может не пройти. Тогда используют метод с бинарным поиском.

Создадим массив: 

vector<int> d;

d[len] хранит минимально возможный последний элемент возрастающей подпоследовательности длины len + 1.

Чем меньше последний элемент, тем легче потом продолжить подпоследовательность.

Идея O(n log n)

Идем по массиву слева направо. Для каждого a[i] находим первую позицию в d, где значение не меньше a[i]. 

auto it = lower_bound(d.begin(), d.end(), a[i]);

Если такой позиции нет, добавляем элемент в конец.

Иначе заменяем найденное значение на a[i].

Почему lower_bound?

Для строго возрастающей подпоследовательности нужно использовать: 

lower_bound

Потому что одинаковые значения не должны увеличивать длину.

strict increasing: 1 2 3
не подходит: 1 2 2 3
Для неубывающей подпоследовательности используют upper_bound.

Реализация O(n log n)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> d;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        auto it = lower_bound(d.begin(), d.end(), x);

        if (it == d.end()) {
            d.push_back(x);
        } else {
            *it = x;
        }
    }

    cout << d.size();

    return 0;
}

Пример работы O(n log n)

Массив: 

5 1 6 2 3 4
Берем d после обработки
5 5
1 1
6 1 6
2 1 2
3 1 2 3
4 1 2 3 4

Длина массива d в конце равна 4. Значит LIS имеет длину 4.

Важно про массив d

Массив d не всегда является настоящей подпоследовательностью из массива.

Он нужен для нахождения длины.

Если нужно восстановить саму LIS в O(n log n), нужно дополнительно хранить позиции и parent.

Строго возрастающая и неубывающая

Тип Условие Бинарный поиск
Возрастающая a1 < a2 < a3 lower_bound
Неубывающая a1 ≤ a2 ≤ a3 upper_bound

LIS через рекурсию

Для понимания можно думать рекурсивно. Пусть: 

solve(i)

Это длина LIS, которая заканчивается в позиции i.

Тогда: 

solve(i) = 1 + max(solve(j)), где j < i и a[j] < a[i]

Рекурсия + мемоизация

int solve(int i) {
    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = 1;

    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], solve(j) + 1);
        }
    }

    return dp[i];
}

Потом ответ: 

for (int i = 1; i <= n; i++) {
    ans = max(ans, solve(i));
}

Полная рекурсивная реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;

int n;
int a[N];
int dp[N];

int solve(int i) {
    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = 1;

    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], solve(j) + 1);
        }
    }

    return dp[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = -1;
    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        ans = max(ans, solve(i));
    }

    cout << ans;

    return 0;
}

Рекурсия → итеративный DP

Рекурсия Итеративный DP
solve(i) dp[i]
solve(j), где j < i dp[j], который уже посчитан
dp[i] = max(solve(j) + 1) dp[i] = max(dp[j] + 1)
вызвать solve для всех i цикл i от 1 до n

Типичные ошибки

  • Думать, что подпоследовательность должна идти подряд
  • Забыть, что порядок элементов менять нельзя
  • Писать a[j] <= a[i] вместо a[j] < a[i] для строго возрастающей LIS
  • Забыть поставить dp[i] = 1
  • Искать ответ только в dp[n], хотя нужно максимум по всем dp[i]
  • Использовать O(n²), когда n слишком большое
  • Думать, что массив d в O(n log n) всегда является настоящей LIS

Асимптотика

Метод Время Память
Рекурсия + мемоизация O(n²) O(n)
Итеративный DP O(n²) O(n)
Бинарный поиск O(n log n) O(n)

Как думать на задачах LIS?

1. Нужно найти длину или саму подпоследовательность?
2. Строго возрастающая или неубывающая?
3. Какое n?
4. Если n маленькое — O(n²)
5. Если n большое — O(n log n)
6. Если нужно восстановление — храним parent

Короткий шаблон O(n²)

int ans = 0;

for (int i = 1; i <= n; i++) {
    dp[i] = 1;

    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    ans = max(ans, dp[i]);
}

cout << ans;

Короткий шаблон O(n log n)

vector<int> d;

for (int i = 0; i < n; i++) {
    auto it = lower_bound(d.begin(), d.end(), a[i]);

    if (it == d.end()) {
        d.push_back(a[i]);
    } else {
        *it = a[i];
    }
}

cout << d.size();