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-тен бұрын тұр. Ал біз порядок өзгерте алмаймыз.

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

DP негізгі идеясы

Массив ойлап табамыз:

dp[i]

dp[i] — i позициясында аяқталатын ең ұзын өсетін подпоследовательность ұзындығы.

Переход қалай жасалады?

dp[i] санау үшін барлық алдыңғы позицияны қараймыз:

j < i

Егер:

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);
    }
}

Финал answer — барлық dp[i] ішіндегі максимум.

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

Қолмен есептеу мысалы

Массив:

5 1 6 2 3 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 позицияларын қараймыз.

Подпоследовательность-тың өзін қалпына келтіру

Кейде тек ұзындығын емес, LIS-тің өзін шығару керек.

Ол үшін сақтаймыз:

parent[i]

parent[i] — i позициясынан бұрын тұрған позиция.

parent қалай жаңартылады?

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

Кейін dp[pos] максималды болатын позицияны табамыз.

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

Answer қалай қалпына келеді?

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²) өтпеуі мүмкін. Ондайда binary search арқылы O(n log 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

қолданылады. Себебі бірдей сандар ұзындықты арттырмауы керек.

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 ұзындығы 4. Демек LIS ұзындығы 4.

d массиві туралы маңызды нәрсе

d массиві әрқашан нақты LIS болмайды. Ол тек ұзындықты табу үшін керек.

Қатаң өсетін және неубывающая

LIS рекурсия арқылы

Түсіну үшін рекурсиямен де ойлауға болады. Мысалы:

solve(i)

Бұл i позициясында аяқталатын LIS ұзындығы.

Онда:

solve(i) = 1 + max(solve(j)), мұнда j < i және a[j] < a[i]

Рекурсия + memoization

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];
}

Кейін answer:

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

Типтік қателер

• Подпоследовательность міндетті түрде қатар тұрады деп ойлау
• Элементтердің реті өзгермеуі керек екенін ұмыту
• Қатаң LIS үшін a[j] <= a[i] деп жазу
• dp[i] = 1 қоюды ұмыту
• Answer тек dp[n] ішінде деп ойлау
• n үлкен кезде O(n²) қолдану
• O(n log n)-дегі d массивін нақты LIS деп ойлау

Асимптотика

LIS задачада қалай ойлау керек?

Қысқа шаблон 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();