Subsecvență maximă în creștere
Acest articol sau secțiune despre subiectul programării nu menționează sursele necesare sau sunt insuficiente. |
În informatică , problema creșterii subsecvenței maxime constă în găsirea unei subsecvențe a unei secvențe date în care elementele subsecvenței sunt ordonate de la cel mai mic la cel mai mare și a căror lungime este maximă posibilă. Subsecvența nu trebuie să fie contiguă sau unică. Problema celei mai mari subsecvențe în creștere poate fi rezolvată în timp O ( n log n ), unde n reprezintă lungimea secvenței originale.
Exemplu
În primii 16 termeni ai secvenței Van der Corput
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
una dintre cele mai mari subsecvențe în creștere este
- 0, 2, 6, 9, 11, 15.
Această subsecvență are șase elemente; secvența originală nu are subsecvențe în creștere de lungime 7 sau mai mult. Cea mai mare subsecvență în creștere în acest caz nu este unică: de exemplu,
- 0, 4, 6, 9, 11, 15 sau 0, 4, 6, 9, 13, 15
Acestea sunt alte subsecvențe în creștere de aceeași lungime și, prin urmare, alte soluții valide la problema în acest caz.
Limite de lungime
Conform teoremei Erdős - Szekeres , fiecare succesiune de n 2 +1 numere întregi distincte are o subsecvență crescătoare sau descrescătoare de lungime n + 1.
