Secvență, subșir sau submulțime? Cum le deosebești
Alege algoritmul pornind de la cerință: poziții consecutive, ordine păstrată sau selecție fără ordine. Vezi exemple și capcane de terminologie.
În acest material
Cuvintele „secvență”, „subșir” și „submulțime” pot conduce la probleme complet diferite. Înainte să alegi o tehnică, verifică două lucruri: elementele trebuie să fie consecutive? Ordinea lor din intrare trebuie păstrată?
Un singur exemplu, trei interpretări
Pornim de la șirul 4 1 7 2. Valorile 1 7 formează un interval consecutiv. Valorile 4 7 2 păstrează ordinea inițială, dar sar peste 1. Valorile 2 4 nu respectă ordinea din șir, deși ambele există în el.
În terminologia folosită aici, o secvență este un interval de poziții consecutive, iar un subșir este obținut prin eliminarea unor poziții, păstrând ordinea celor rămase. O submulțime este o selecție în care ordinea nu contează. Enunțul concret are prioritate: în unele materiale, termenii sunt utilizați diferit sau problema vorbește despre o selecție de poziții, cu repetiții de valori.
În 4,1,7,2, valorile 1,7 sunt secvență, 4,7,2 sunt subșir, iar 2,4 pot descrie o submulțime.Mărește schema ↗
Testul celor două frontiere
Dacă soluția poate fi descrisă complet prin început și sfârșit, iar toate pozițiile dintre ele sunt incluse, ai o secvență. Pentru un vector de n elemente, există n(n+1)/2 secvențe nevide. Formula numără poziții, chiar dacă unele valori sunt egale.
O sumă pe un astfel de interval poate fi obținută din sume prefix. Dacă lungimea este fixă, o fereastră glisantă poate actualiza suma. Dacă lungimea este liberă și cauți suma maximă, problema cere o altă analiză, de exemplu algoritmul Kadane.
Când poți sări peste elemente
Pentru un subșir crescător, nu este obligatoriu ca valorile alese să fie vecine. În 1 9 2 3, un subșir strict crescător este 1 2 3, de lungime 3. Cea mai lungă secvență strict crescătoare are lungimea 2. Aceeași intrare separă clar cele două cerințe.
Sortarea înainte de rezolvare nu păstrează problema subșirului: schimbă ordinea inițială și poate crea soluții care nu existau. Dacă algoritmul tău sortează, justifică explicit de ce cerința permite asta.
Repetițiile cer o definiție atentă
În 2 2 3, alegerea primei valori 2 și alegerea celei de-a doua sunt selecții de poziții diferite, dar pot produce același șir de valori. Când numeri soluții, enunțul trebuie să precizeze ce se consideră distinct. Nu folosi automat puteri ale lui 2 fără să verifici dacă numeri poziții, valori distincte sau mulțimi matematice.
Cum alegi exercițiul următor
Rescrie cerința în limbaj simplu: „aleg un interval”, „pot sări, dar nu reordonez” sau „aleg elemente fără condiție de ordine”. Apoi construiește un exemplu în care aceste interpretări produc răspunsuri diferite. Dacă nu poți face asta, mai clarifică modelul înainte de cod.
Compară direct secvențele și sumele prefix, subșirul crescător maxim și combinările și submulțimile. Pentru două șiruri, continuă cu subșirul comun maxim.
Întrebări frecvente
Ce este o secvență de elemente într-un șir?
În convenția folosită aici, este un interval de poziții consecutive. Din 4 1 7 2, valorile 1 7 formează o secvență, iar 4 7 nu, deoarece sar peste un element.
Care este diferența dintre secvență și subșir?
O secvență cere poziții consecutive. Un subșir păstrează ordinea inițială, dar poate sări peste poziții. Verifică definiția din enunț, deoarece terminologia poate varia între surse.
De ce contează dacă problema cere o submulțime?
O submulțime nu păstrează o ordine a elementelor, spre deosebire de un subșir. Clarifică și tratamentul duplicatelor: alegerea pozițiilor dintr-un vector nu este întotdeauna aceeași problemă cu alegerea valorilor distincte.