Subșir crescător de lungime maximă în C++

Un subșir păstrează ordinea elementelor, dar poate să sară poziții. Cerem un subșir strict crescător cu lungime maximă, numit frecvent LIS. Nu este același lucru cu o secvență consecutivă crescătoare și nici cu sortarea vectorului.

Sortarea ar schimba ordinea inițială și ar produce un răspuns pentru altă problemă. Programarea dinamică păstrează această ordine prin tranziții numai din poziții anterioare.

Cum funcționează

Definim d[i] ca lungimea maximă a unui subșir crescător care se termină exact la poziția i. Fiecare element poate forma singur un subșir, deci inițial d[i]=1. Pentru orice j<i cu a[j]<a[i], putem extinde un subșir terminat în j: candidatul are lungimea d[j]+1.

Alegem candidatul cel mai lung și memorăm în p[i] poziția precedentă. Această informație permite reconstruirea unei soluții, nu doar calcularea lungimii. Răspunsul global este maximul tuturor d[i], deoarece soluția optimă se poate termina oriunde, nu obligatoriu în ultimul element.

Comparația strictă exclude valorile egale. Dacă problema cere un subșir nedescrescător, o înlocuim cu <= și schimbăm corespunzător explicația. Acesta nu este un detaliu cosmetic: pentru 5,5,5 lungimea strict crescătoare este unu, dar lungimea nedescrescătoare este trei.

Exemplu urmărit pas cu pas

Pentru 3,1,2,5,4, valorile d sunt 1,1,2,3,3. Elementul 2 poate extinde subșirul care se termină în 1. Atât 5, cât și 4 pot continua cu o a treia valoare. Implementarea păstrează primul maxim global, deci reconstruiește 1,2,5.

Există și soluția 1,2,4, cu aceeași lungime. Faptul că un evaluator acceptă o soluție trebuie interpretat conform cerinței: unele probleme cer doar lungimea, altele orice subșir optim, iar altele cer un criteriu suplimentar de departajare. Programul presupune 1 <= n <= 100.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, a[100], d[100], p[100], route[100];
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    int best = 0;
    for (int i = 0; i < n; ++i) {
        d[i] = 1;
        p[i] = -1;
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i] && d[j] + 1 > d[i]) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        if (d[i] > d[best])
            best = i;
    }
    int count = 0;
    for (int i = best; i != -1; i = p[i])
        route[count++] = a[i];
    std::cout << count << '\n';
    for (int i = count - 1; i >= 0; --i)
        std::cout << route[i] << (i == 0 ? '\n' : ' ');
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n;
    std::vector<int> a(100), d(100), p(100), route(100);
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    int best = 0;
    for (int i = 0; i < n; ++i) {
        d[i] = 1;
        p[i] = -1;
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i] && d[j] + 1 > d[i]) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        if (d[i] > d[best])
            best = i;
    }
    int count = 0;
    for (int i = best; i != -1; i = p[i])
        route[count++] = a[i];
    std::cout << count << '\n';
    for (int i = count - 1; i >= 0; --i)
        std::cout << route[i] << (i == 0 ? '\n' : ' ');
}

De ce funcționează și cât costă

Orice subșir crescător terminat în i fie conține numai a[i], fie are un penultim element într-o poziție j eligibilă. Tranziția examinează toate aceste posibilități. Valorile d[j] sunt deja corecte deoarece j<i, deci alegerea maximului produce exact optimul stării i.

Implementarea are O(n²) timp și O(n) memorie pentru stări, părinți și traseu. Există și o metodă O(n log n) bazată pe cele mai mici capete posibile și căutare binară; acea listă de capete nu este, singură, un subșir reconstruit.

Greșeli frecvente

Nu returna automat d[n-1]. Nu folosi sortarea ca înlocuitor al analizei ordinii. La reconstruire, p[i]=-1 indică începutul; accesarea p[-1] ar ieși din domeniul tabloului.

Exersează

Calculează lungimea maximă pentru 8,6,4,2 și pentru 1,2,3,4. Explică stările în cele două cazuri.

Rezolvare explicată: În primul caz fiecare stare rămâne unu, fiindcă nu există un predecessor mai mic. În al doilea, stările sunt 1,2,3,4, deoarece fiecare element îl poate continua pe precedentul.

Continuă să înveți

Secvențe, programare dinamică și căutare binară.

Întrebări frecvente

Care este diferența dintre subșir și secvență?

Subșirul poate omite elemente, dar păstrează ordinea. Secvența folosește poziții consecutive. Algoritmii și răspunsurile pot fi complet diferite.

De ce definim starea ca terminând exact în i?

Această condiție spune ce valoare va preceda următorul element. Fără ea, nu am ști dacă un rezultat global anterior poate fi extins.

Ce fac cu elementele egale?

Pentru creștere strictă nu le legi printr-o tranziție. Pentru varianta nedescrescătoare sunt permise, dar trebuie schimbată explicit condiția comparației.

Cum reconstruiesc un subșir optim?

Păstrezi poziția precedentă pentru fiecare îmbunătățire, pornești de la un indice cu lungime maximă și urmărești părinții. Apoi inversezi ordinea.

Pot exista mai multe soluții optime?

Da. Lungimea maximă poate fi obținută prin subșiruri diferite. Un criteriu precum cel mai mic lexicografic necesită o analiză suplimentară.