← Назад к ДП

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

Поиск длины и восстановление последовательности за O(n log n)

🐍 Python
import bisect

INF = 10**9 + 7
n = int(input())
A = list(map(int, input().split()))

dp = [INF] * (n + 1)
dp[0] = -INF
pos = [-1] * (n + 1)
prev = [-1] * (n + 1)
l = 0

for i in range(n):
    j = bisect.bisect_left(dp, A[i])
    if dp[j - 1] < A[i] and A[i] < dp[j]:
        dp[j] = A[i]
        pos[j] = i
        prev[i] = pos[j - 1]
        l = max(l, j)

ANS = []
p = pos[l]
while p != -1:
    ANS.append(A[p])
    p = prev[p]
ANS = list(reversed(ANS))

print(l)
print(*ANS)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    vector<int> dp(n + 1, INF);
    vector<int> pos(n + 1, -1);
    vector<int> prev(n, -1);
    
    dp[0] = -INF;
    int l = 0;
    
    for (int i = 0; i < n; i++) {
        int j = lower_bound(dp.begin(), dp.end(), A[i]) - dp.begin();
        if (dp[j - 1] < A[i] && A[i] < dp[j]) {
            dp[j] = A[i];
            pos[j] = i;
            prev[i] = pos[j - 1];
            l = max(l, j);
        }
    }
    
    vector<int> ANS;
    int p = pos[l];
    while (p != -1) {
        ANS.push_back(A[p]);
        p = prev[p];
    }
    reverse(ANS.begin(), ANS.end());
    
    cout << l << endl;
    for (int i = 0; i < (int)ANS.size(); i++) {
        cout << ANS[i] << " ";
    }
    
    return 0;
}
Сравнение реализаций: Существует также реализация НВП за O(n²), которая проще для понимания, но работает медленнее на больших массивах.

Как работает алгоритм НВП за O(n log n)?

НВП (Longest Increasing Subsequence) — это задача поиска самой длинной подпоследовательности, в которой элементы идут в строго возрастающем порядке.

Основная идея оптимизации

Вместо хранения длины подпоследовательности для каждого элемента, мы храним минимальный возможный последний элемент для подпоследовательности каждой длины.

Шаги алгоритма

  1. Инициализируем dp[0] = -INF (фиктивный элемент)
  2. Для каждого элемента A[i] находим позицию j = lower_bound(dp, A[i]) — первую позицию, где dp[j] >= A[i]
  3. Если A[i] можно вставить между dp[j-1] и dp[j], обновляем dp[j] = A[i]
  4. Сохраняем индексы для восстановления ответа

Временная сложность: O(n log n) — бинарный поиск на каждом шаге.

Пространственная сложность: O(n) — массивы dp, pos, prev.

Пример работы

Рассмотрим массив: A = [3, 1, 4, 2, 5]

Пошаговое выполнение:

Инициализация: dp[0] = -∞, dp[1..5] = ∞

i=0, A[0]=3: lower_bound(3) = 1
       dp[0]=-∞ < 3 < ∞ → dp[1]=3, pos[1]=0, prev[0]=pos[0]=-1

i=1, A[1]=1: lower_bound(1) = 1
       dp[0]=-∞ < 1 < 3 → dp[1]=1, pos[1]=1, prev[1]=pos[0]=-1

i=2, A[2]=4: lower_bound(4) = 2
       dp[1]=1 < 4 < ∞ → dp[2]=4, pos[2]=2, prev[2]=pos[1]=1

i=3, A[3]=2: lower_bound(2) = 2
       dp[1]=1 < 2 < 4 → dp[2]=2, pos[2]=3, prev[3]=pos[1]=1

i=4, A[4]=5: lower_bound(5) = 3
       dp[2]=2 < 5 < ∞ → dp[3]=5, pos[3]=4, prev[4]=pos[2]=3

Результат: l = 3
Восстановление: pos[3]=4 → A[4]=5
                prev[4]=3 → A[3]=2
                prev[3]=1 → A[1]=1
Ответ: 1 2 5 (длина 3)

Длина наибольшей возрастающей подпоследовательности: 3
Сама последовательность: 1 2 5

Попробовать алгоритм онлайн

Введите массив чисел и найдите НВП:

Результат появится здесь...