En Uzun Artan Alt Dizi
O(n^2) DP ve ardından O(n log n) hilesi.
En Uzun Artan Alt Dizi, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
LIS Nedir
Bir alt dizi sıralamayı korur ancak bazı öğeleri atlar. En uzun artan alt dizi, değerleri kesin olarak artan en uzun alt dizidir.
a = [3, 1, 4, 1, 5, 9, 2]Alt Dizi, Alt Dizi Parçası Değil
Bir alt dizi parçasının aksine, bir LIS'in ardışık olması gerekmez. Zinciri büyütmek için daha küçük sayıların üzerinden atlayabilirsiniz.
O(n^2) DP Durumu
dp[i], i indeksinde sona eren LIS'in uzunluğu olsun. Her öğe, tek başına en az bir uzunluğunda bir alt dizidir.
dp = [1] * nO(n^2) Geçişi
Her i için kendisinden önceki tüm j değerlerine bakın. a[j] daha küçükse diziyi uzatın: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Yanıtı Tablodan Okuyun
LIS yalnızca son indekste değil, herhangi bir yerde sona erebileceği için sonuç tablodaki en büyük değerdir.
answer = max(dp)O(n^2) Neden TLE Olabilir
İç içe iki döngünün maliyeti O(n kare) olur. n değeri 100000'e yaklaştığında bu çok yavaştır ve zaman sınırı kararıyla sonuçlanır.
Sabır Sıralaması Fikri
Daha hızlı yöntem, sabır sıralamasında olduğu gibi her alt dizi uzunluğu için mümkün olan en küçük son değeri içeren bir liste tutar.
tails = []Yerleştirmek İçin İkili Arama Kullanın
Her sayı için son değerler arasında uygun yeri bisect_left ile ikili arayarak bulun; böylece toplam karmaşıklık O(n log n) olur.
from bisect import bisect_leftUzatın veya Değiştirin
Yuva listenin sonrasındaysa LIS'i büyütmek için append kullanın. Aksi durumda o son değeri daha küçük değerle değiştirin.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xUzunluk tails Dizisindedir
Tarama sona erdiğinde len(tails), LIS'in uzunluğudur. Listenin kendisi her zaman alt dizinin kendisi değildir; yalnızca uzunluğu kesindir.
answer = len(tails)Kesin Artan ve Azalmayan
Azalmayan sürüm için bisect_right kullanın; böylece eşit değerler zinciri uzatabilir.
from bisect import bisect_rightHızlı Kontrol
LIS uzunluğunu O(n log n) sürede hangi yöntem bulur?
Özet: n^2'den n log n'ye
Artık LIS'i iki şekilde çözebilirsiniz. O(n^2) DP basittir; son değerler ve ikili arama yöntemi büyük girdilere ölçeklenir ve zaman sınırını aşmaz.
Sıkça Sorulan Sorular
“En Uzun Artan Alt Dizi” dersi ücretsiz mi?
Evet — “En Uzun Artan Alt Dizi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“En Uzun Artan Alt Dizi” dersinde ne öğreneceğim?
O(n^2) DP ve ardından O(n log n) hilesi. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“En Uzun Artan Alt Dizi” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Memoization ve Tabulation Karşılaştırması
- Durumu ve Geçişi Tanımlama
- Merdiven Çıkma ve Para Kombinasyonları
- En Uzun Artan Alt Dizi