Cel mai lung subșir crescător (LIS)
Alegeți numere dintr-o listă, de la stânga la dreapta, fiecare mai mare decât precedentul. Cât de lung poate deveni un astfel de lanț? Întrebarea este destul de simplă pentru o carte de enigme, iar răspunsul ei leagă un joc de cărți, un tabel clasic de programare dinamică și unul dintre cele mai frumoase rezultate despre amestecările aleatoare.
Problema
Dată fiind o listă de numere, un subșir păstrează o parte dintre ele în ordinea lor inițială. Este crescător dacă fiecare valoare este mai mare decât precedenta. Cel mai lung subșir crescător, sau LIS, este cea mai lungă alegere de acest fel. O listă de n valori are 2ⁿ subșiruri, deci verificarea tuturor funcționează doar pentru liste foarte scurte.
Tabelul
Fie len[i] lungimea celui mai lung subșir crescător care se termină exact la poziția i. Ea este 1 pentru valoarea singură sau 1 + len[j] pentru o poziție anterioară j a cărei valoare este mai mică, oricare este mai mare. Fiecare poziție se uită înapoi la toate cele anterioare, deci tabelul are nevoie de n·(n − 1)/2 comparații. Răspunsul este cel mai mare len[i], iar notarea lui j care a dat fiecare len[i] permite citirea subșirului înapoi.
Un exemplu
Luați 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Poziție cu poziție, lungimile sunt 1, 2, 1, 1, 3, 2, 3, 4, 3 și 5: 20 prelungește 3, 10; 4 prelungește 3; 6 prelungește 4, 7 prelungește 6, iar 9 prelungește 7. Citind înapoi de la 9 se obține 3, 4, 6, 7, 9, un subșir crescător de lungime 5.
O metodă mai rapidă: sortarea pasians
Împărțiți valorile ca pe niște cărți în teancuri: fiecare valoare merge pe teancul cel mai din stânga al cărui vârf nu este mai mic decât ea sau începe un teanc nou în dreapta. Numărul de teancuri este lungimea LIS. Deoarece vârfurile teancurilor sunt mereu sortate, teancul potrivit poate fi găsit prin căutare binară, deci întreaga metodă ia O(n log n) pași. Își trage numele de la jocul de pasians (în engleză, patience) cu care seamănă.
Puțină matematică
În 1935, Paul Erdős și George Szekeres au demonstrat că orice listă de n² + 1 numere diferite are un subșir crescător sau unul descrescător de lungime n + 1. Stanislaw Ulam a întrebat în 1961 cât de lung este LIS al unei amestecări aleatoare a n numere. Răspunsul, apropiat de 2√n pentru n mare, a fost stabilit în 1977 de Anatoly Vershik și Sergei Kerov, precum și de Ben Logan și Larry Shepp, iar în 1999 Jinho Baik, Percy Deift și Kurt Johansson au găsit forma exactă a fluctuațiilor sale: distribuția Tracy–Widom din teoria matricelor aleatoare.
Explorați
Deschideți aplicația și apăsați Pas. Coloana portocalie este poziția care se calculează, iar coloana albastră este poziția anterioară cu care este comparată. Rândul Lungime crește pe măsură ce se găsesc lanțuri mai lungi, rândul Vine după ține minte de unde provin, iar la final răspunsul este citit înapoi cu portocaliu și afișat sub tabel.
Întrebări frecvente
Care este complexitatea în timp a LIS?
O(n²) cu tabelul, pentru că fiecare poziție se uită la toate cele anterioare, și O(n log n) cu sortarea pasians și căutarea binară. Ambele au nevoie de O(n) memorie.
Cum găsesc cel mai lung subșir nedescrescător?
Lăsați o valoare să vină după una egală: comparați cu ≤ în loc de <. În aplicație, bifați Permite valori egale. La sortarea pasians, puneți fiecare valoare pe teancul cel mai din stânga al cărui vârf este strict mai mare.
Ce este cel mai lung subșir descrescător?
Aceeași problemă cu comparația inversată, sau LIS al listei în care fiecare valoare și-a schimbat semnul. Conform teoremei Erdős–Szekeres, o listă suficient de lungă are mereu un subșir crescător lung sau un subșir descrescător lung.
Cât de lung este LIS al unei liste aleatoare?
Pentru o amestecare aleatoare a n numere diferite, aproape 2√n pentru n mare. Corecția crește ca rădăcina de ordinul șase din n, deci pentru o mie de numere media este în jur de 58, puțin sub 2√1000 ≈ 63.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați cel mai lung subșir crescător