Nejdelší rostoucí podposloupnost

O(n²)

Nejdelší rostoucí podposloupnost (LIS) je nejdelší množina prvků pole, vzatých v původním pořadí, jejichž hodnoty striktně rostou — nemusí být vedle sebe. DP v O(n²) drží dp[i] = délku nejlepší rostoucí podposloupnosti, která končí přesně na indexu i. Při vyplňování se každý prvek ohlédne na všechny dřívější prvky menší než on sám a prodlouží jejich nejdelší běh, přičemž si ukazatel na rodiče zapamatuje volbu, aby šlo skutečnou podposloupnost na konci vystopovat. Odpovědí je největší hodnota dp. (Existuje chytřejší verze v O(n log n) pomocí patience sortu.) LIS se objevuje v diffu, skládání krabic i analýze trpělivostních her.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Každému prvku dej podposloupnost délky 1 (sám sebe).
  2. Pro každý prvek se ohlédni na všechny dřívější menší prvky.
  3. Prodluž nejdelší nalezený běh a zapamatuj si toho předchůdce.
  4. Vyhrává největší délka; projdi ukazatele na rodiče zpět pro podposloupnost (zvýrazněna).

Pseudokód

1lis(a):                             # O(n²)2  dp[i] ← 1 for all i               # each element alone3  for i in 0..n-1:4    for j in 0..i-1:5      if a[j] < a[i] and dp[j]+1 > dp[i]:6        dp[i] ← dp[j] + 1            # extend the best run ending at j7        parent[i] ← j8  answer ← max(dp)                   # walk parents back for the actual run