Celule completate
Comparații
Cel mai lung până acum

  • Se completează
  • Citită
  • Răspuns

Mai multe despre cel mai lung subșir crescător

Cel mai lung subșir crescător (LIS)

Într-o listă de numere, câte puteți alege, păstrându-le ordinea, astfel încât fiecare să fie mai mare decât precedentul? Cel mai lung subșir crescător răspunde la această întrebare. Introduceți o listă și urmăriți cum programarea dinamică află, pentru fiecare poziție, cel mai lung lanț care se termină acolo. Apăsați Redare pentru a urmări cum se completează tabelul sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Introduceți o listă de numere. Pentru fiecare poziție, tabelul reține lungimea celui mai lung lanț crescător de valori care se termină acolo și poziția anterioară pe care o continuă. Bifați Permite valori egale pentru lanțuri care nu coboară niciodată. La final, lanțul este citit înapoi pornind de la ultima sa valoare. Exemplu nou creează altă listă. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Introduceți o listă de numere, separate prin virgule sau spații. Bifați Permite valori egale pentru lanțuri care nu coboară niciodată.
  2. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde.
  3. Urmăriți cum fiecare poziție este comparată cu toate cele anterioare, apoi vedeți cel mai lung lanț citit înapoi cu portocaliu.

Cum funcționează tabelul

Tabelul are trei rânduri: valorile, lungimea celui mai lung subșir crescător care se termină la fiecare poziție și poziția pe care acesta o continuă. O valoare singură este un lanț de lungime 1. Apoi se verifică fiecare poziție anterioară: dacă valoarea ei este mai mică, lanțul care se termină acolo poate fi prelungit cu această valoare, iar lungimea crește cu unu. Câștigă cea mai lungă astfel de prelungire, iar poziția ei trece în al treilea rând.

Citirea lanțului înapoi

Cel mai lung subșir crescător se termină la poziția cu cea mai mare lungime. De acolo, al treilea rând spune ce poziție vine înainte, iar al treilea rând al acelei poziții spune care vine înaintea ei, până la o poziție fără predecesor. Citite în ordine, aceste valori sunt răspunsul. Cu Permite valori egale bifat, o valoare poate veni și după una egală, ceea ce dă cel mai lung lanț care nu coboară niciodată.

Întrebări frecvente

Care este diferența dintre un subșir și o subsecvență?

O subsecvență este un bloc de valori vecine. Un subșir păstrează ordinea, dar poate sări peste valori, așa că în 3, 10, 2, 1, 20 valorile 3, 10 și 20 formează un subșir crescător, deși 2 și 1 se află între ele.

Cât de rapid este algoritmul LIS?

Metoda tabelului compară fiecare pereche de poziții: n·(n − 1)/2 comparații pentru n valori. Sortarea pasians reușește în O(n log n): reține, pentru fiecare lungime, cea mai mică valoare care încheie un lanț de acea lungime și plasează fiecare valoare nouă prin căutare binară.

Este cel mai lung subșir crescător unic?

Nu întotdeauna. În 1, 3, 2, 4, atât 1, 3, 4, cât și 1, 2, 4 au lungimea 3. Tabelul dă lungimea, iar citirea înapoi găsește unul dintre ele.

Unde se folosește cel mai lung subșir crescător?

La compararea fișierelor și a genomurilor, unde unele metode găsesc mai întâi liniile care se potrivesc și apoi iau un subșir crescător al pozițiilor lor; în planificare și în problemele de stivuire a cutiilor; și în matematică, unde lungimea LIS a unei amestecări aleatoare este un obiect de studiu celebru.

Se trimite ceva undeva?

Nu. Totul se calculează în browserul dumneavoastră, iar ultimele setări rămân în spațiul de stocare local al acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor