← Назад к ДП

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

Поиск самой длинной возрастающей подпоследовательности за O(n²)

🐍 Python
n = int(input())
A = list(map(int, input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))
⚙️ C++
#include <bits/stdc++.h>
using namespace std;
using T = long long;

int main() {
    T n, i, j;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    vector<T> dp(n, 1);
    vector<T> A(n);
    
    for (i = 0; i < n; i++) {
        cin >> A[i];
        for (j = 0; j < i; j++) {
            if (A[i] > A[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

Как работает алгоритм НВП?

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

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

Основная идея динамического программирования

Временная сложность: O(n²) — два вложенных цикла по n элементов.

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

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

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

Пошаговый расчёт dp:

Инициализация: dp = [1, 1, 1, 1, 1]

i=0, A[0]=3: нет предыдущих элементов → dp[0]=1

i=1, A[1]=1: сравниваем с j=0 (A[0]=3)
       3 < 1? нет → dp[1]=1

i=2, A[2]=4: сравниваем с j=0 (3<4? да) → dp[2]=max(1,1+1)=2
               с j=1 (1<4? да) → dp[2]=max(2,1+1)=2

i=3, A[3]=2: сравниваем с j=0 (3<2? нет)
               с j=1 (1<2? да) → dp[3]=max(1,1+1)=2
               с j=2 (4<2? нет)

i=4, A[4]=5: сравниваем с j=0 (3<5? да) → dp[4]=max(1,1+1)=2
               с j=1 (1<5? да) → dp[4]=max(2,1+1)=2
               с j=2 (4<5? да) → dp[4]=max(2,2+1)=3
               с j=3 (2<5? да) → dp[4]=max(3,2+1)=3

Результат: dp = [1, 1, 2, 2, 3]
Ответ: max(dp) = 3 (подпоследовательности: 1→4→5 или 1→2→5 или 3→4→5)

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

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

Введите массив чисел и найдите длину наибольшей возрастающей подпоследовательности:

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