longest increasing subsequence

Angol

Főnév

longest increasing subsequence (tsz. longest increasing subsequences)

1. (informatika)

A leghosszabb növekvő részsorozat (Longest Increasing Subsequence, LIS) egy olyan klasszikus probléma a számítástudományban, amelyben egy adott sorozatból kell kiválasztani egy olyan részsorozatot, amely növekvő és a lehető leghosszabb. Ezt gyakran dinamikus programozással vagy bináris kereséssel optimalizált módszerekkel oldják meg.

Probléma megfogalmazása

Adott egy n hosszúságú A számsorozat. Meg kell találni a leghosszabb olyan részsorozatot, amelyben a számok szigorúan növekednek.

Példa

Bemenet:

A = {10, 22, 9, 33, 21, 50, 41, 60, 80}

Kimenet:

A leghosszabb növekvő részsorozat hossza: 6

Egy lehetséges LIS:

{10, 22, 33, 50, 60, 80}

---

Megoldási módszerek

1. Naiv rekurzív megoldás (Exponenciális idő)

Ez a módszer minden lehetséges részsorozatot kipróbál, és megnézi, melyik a leghosszabb növekvő.

Lépések: 1. Azt vizsgáljuk, hogy egy adott elem része legyen-e az LIS-nek. 2. Rekurzívan ellenőrizzük a többi elemet.

Időbonyolultság: ( O(2^n) ), ami túl lassú nagy n értékekre.

2. Dinamikus programozás (O(n²))

Ebben a módszerben egy dp tömböt használunk, ahol dp[i] azt jelenti, hogy az i-edik elemig tartó LIS hossza.

Algoritmus: 1. Minden i-edik elemre visszatekintünk az előzőekre. 2. Ha A[j] < A[i], akkor dp[i] = max(dp[i], dp[j] + 1). 3. A legnagyobb dp[i] érték lesz az eredmény.

C++ kód:

#include <iostream>
#include <vector>
using namespace std;

int longestIncreasingSubsequence(vector<int>& A) {
    int n = A.size();
    vector<int> dp(n, 1);
    int maxLength = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (A[j] < A[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLength = max(maxLength, dp[i]);
    }
    return maxLength;
}

int main() {
    vector<int> A = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << "A leghosszabb növekvő részsorozat hossza: " << longestIncreasingSubsequence(A) << endl;
    return 0;
}

Időbonyolultság: ( O(n^2) )

3. Bináris keresés + Patience Sorting (O(n log n))

Ebben a módszerben egy segédvektort (sub) tartunk fenn, amely a növekvő részsorozatot reprezentálja.

Algoritmus: 1. Minden A[i] számot megpróbálunk elhelyezni a sub vektorban. 2. Ha A[i] nagyobb, mint a sub utolsó eleme, hozzáadjuk a végéhez. 3. Ha kisebb, akkor a sub-ban bináris kereséssel megkeressük a helyét, és lecseréljük. 4. A sub mérete lesz az LIS hossza.

C++ kód:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestIncreasingSubsequence(vector<int>& A) {
    vector<int> sub;
    for (int num : A) {
        auto it = lower_bound(sub.begin(), sub.end(), num);
        if (it == sub.end()) {
            sub.push_back(num);
        } else {
            *it = num;
        }
    }
    return sub.size();
}

int main() {
    vector<int> A = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << "A leghosszabb növekvő részsorozat hossza: " << longestIncreasingSubsequence(A) << endl;
    return 0;
}

Időbonyolultság: ( O(n log n) )

---

Összehasonlítás

Módszer	Időbonyolultság	Tárbonyolultság
Naiv rekurzió	( O(2^n) )	( O(1) )
Dinamikus programozás	( O(n^2) )	( O(n) )
Bináris keresés	( O(n log n) )	( O(n) )

A bináris kereséses megoldás a leggyorsabb nagy n értékekre, de ha az egész LIS-t ki kell írni, akkor a dinamikus programozásos módszer jobb lehet.

---

Feladatok gyakorlásra

1. Implementáld az LIS algoritmusokat és teszteld különböző bemeneteken!
2. Próbáld meg kiíratni a tényleges LIS-t az O(n log n) algoritmusban!
3. Hogyan változna az algoritmus, ha nem szigorúan növekvő, hanem nem csökkenő részsorozatot keresnénk?

További információk

• longest increasing subsequence - Szótár.net (en-hu)
• longest increasing subsequence - Sztaki (en-hu)
• longest increasing subsequence - Merriam–Webster
• longest increasing subsequence - Cambridge
• longest increasing subsequence - WordNet
• longest increasing subsequence - Яндекс (en-ru)
• longest increasing subsequence - Google (en-hu)
• longest increasing subsequence - Wikidata
• longest increasing subsequence - Wikipédia (angol)