secvmin

Algoritmul, pas cu pas

A număra direct toate perechile $(x, y)$ ar însemna $O(n^2)$ — prea mult pentru $n$ până la un milion. Trucul e să fixăm capătul drept $y$ și să numărăm dintr-o singură mișcare câte capete stânga $x$ formează o subsecvență validă cu acel $y$.

Întrebarea cheie: pornind de la $y$ și mergând spre stânga, până unde putem alege $x$ astfel încât subsecvența $[x, y]$ să conțină toate cele $k$ valori cerute? Răspunsul depinde de unde a apărut ultima dată fiecare valoare cerută.