En Uzun Artan Alt Dizi
Dinamik Programlama O(n²) O(n)Kesin artan (bitişik olması gerekmeyen) en uzun değer dizisi; dp[i] = i'de biten en iyi alt dizi ile.
1/55
dp[0] = 1 — 10 tek başına.
Değişmezdp[i], tam olarak i'de biten en uzun artan dizidir.
lis.c
int lis(int a[], int n) {int dp[n];int best = 0;for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (a[j] < a[i] && dp[j] + 1 > dp[i])dp[i] = dp[j] + 1;}if (dp[i] > best) best = dp[i];}return best;}
En Uzun Artan Alt Dizi nasıl çalışır?
dp[i] = tam i'de biten en uzun artan dizinin uzunluğu. Her i için geriye bak, daha küçük her elemanın en iyi dizisini uzat. Yanıt tüm bitişlerin maksimumudur.
En kötü durum
Gösterildiği gibi O(n²); O(n log n)'lik patience-sorting türevi vardır.
Ne zaman kullanılır?
En uzun eğilim tespiti, patience sorting, kutu istifleme tarzı problemler.