En Uzun Artan Alt Dizi (LIS)

#Nasıl çalışır?

En uzun artan alt dizi (LIS), bir sayı dizisinden bazı elemanları silerek elde edilebilecek, kesin artan en uzun alt dizidir. [3, 10, 2, 1, 20, 4, 6, 7] için cevap [3, 4, 6, 7]'dir (uzunluk 4).

dp[i], a[i] ile biten en uzun artan alt dizinin uzunluğudur. a[i]'den önce gelen ve ondan küçük her a[j] için a[i], j ile biten diziyi uzatabilir: dp[i] = 1 + max(dp[j]). Hiçbiri yoksa dp[i] = 1.

prev[i] hangi j'nin uzatıldığını tutar; en büyük dp değerinden geriye doğru prev[] izlenerek alt dizinin kendisi bulunur. Daha hızlı bir yöntem de vardır: her uzunluk için en küçük bitiş değeri tutulur ve ikili aramayla O(n log n)'e inilir.

#Kendin dene

#Adım adım

1. 01Her dp[i] = 1 ile başla.
2. 02Her i için kendisinden önceki her j'ye bak: a[j] < a[i] ve dp[j] + 1 > dp[i] ise dp[i] = dp[j] + 1, prev[i] = j.
3. 03Cevap dp'deki en büyük değerdir.
4. 04O konumdan prev[] zincirini izleyerek alt diziyi geriye doğru oku.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def lis(a: list) -> list:
    n = len(a)
    dp = [1] * n        # dp[i] = longest increasing subsequence ending at a[i]
    prev = [-1] * n     # the element before a[i] in that subsequence
    for i in range(1, n):
        for j in range(i):
            if a[j] < a[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    i = dp.index(max(dp))
    out = []
    while i != -1:
        out.append(a[i])
        i = prev[i]
    return out[::-1]


result = lis([3, 10, 2, 1, 20, 4, 6, 7])
print(len(result))
print(" ".join(map(str, result)))

#Karmaşıklık

Her i için önceki tüm j'lere bakıldığı için O(n²)'dir. tails[k] = uzunluğu k + 1 olan artan dizilerin en küçük son elemanı tutularak her sayı ikili aramayla yerleştirilir ve O(n log n)'e inilir.

#Ne zaman kullanılır?

Zaman serilerinde en uzun yükseliş eğilimi, kutu iç içe yerleştirme (Russian doll) problemleri, sürüm ve değişiklik kayıtlarında en uzun tutarlı sıra ve patience sorting kart oyunu LIS fikrine dayanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.