- Dolduruluyor
- Okunan
- Cevap
En uzun artan alt dizi (LIS)
Bir sayı listesinden, sıralarını koruyarak ve her biri bir öncekinden büyük olacak şekilde kaç sayı seçebilirsiniz? En uzun artan alt dizi bu sorunun cevabıdır. Bir liste yazın ve dinamik programlamanın her konum için orada biten en uzun diziyi nasıl bulduğunu izleyin. Tablonun dolmasını izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Bir sayı listesi yazın. Tablo her konum için, o konumda biten en uzun artan değer dizisinin uzunluğunu ve bu dizinin devam ettirdiği önceki konumu tutar. Hiç azalmayan diziler için Eşit değerlere izin ver kutusunu işaretleyin. Sonunda dizi, son değerinden başlayarak geriye doğru okunur. Yeni örnek başka bir liste oluşturur. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Virgül veya boşlukla ayırarak bir sayı listesi yazın. Hiç azalmayan diziler için Eşit değerlere izin ver kutusunu işaretleyin.
- Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
- Her konumun önceki tüm konumlarla karşılaştırılmasını izleyin, ardından en uzun dizinin turuncu renkle geriye doğru okunmasını görün.
Tablo nasıl çalışır
Tablonun üç satırı vardır: değerler, her konumda biten en uzun artan alt dizinin uzunluğu ve bu dizinin devam ettirdiği konum. Tek başına bir değer, uzunluğu 1 olan bir dizidir. Sonra önceki her konum kontrol edilir: değeri daha küçükse, orada biten dizi bu değerle uzatılabilir ve uzunluğu bir artar. Bu uzatmalardan en uzunu kazanır ve onun konumu üçüncü satıra yazılır.
Diziyi geriye doğru okumak
En uzun artan alt dizi, uzunluğu en büyük olan konumda biter. Oradan başlayarak üçüncü satır, kendinden önce hangi konumun geldiğini söyler; o konumun üçüncü satırı da ondan öncekini söyler. Bu, öncesi olmayan bir konuma gelene kadar sürer. Bu değerler sırayla okunduğunda cevabı verir. Eşit değerlere izin ver işaretliyken bir değer kendisine eşit bir değerin ardından da gelebilir; bu da hiç azalmayan en uzun diziyi verir.
Sık sorulan sorular
Alt dizi ile ardışık alt dizi arasındaki fark nedir?
Ardışık alt dizi, yan yana duran değerlerden oluşan bir bloktur. Alt dizi ise sırayı korur ama değer atlayabilir; bu yüzden 3, 10, 2, 1, 20 listesinde, aralarında 2 ve 1 olsa da 3, 10 ve 20 değerleri artan bir alt dizi oluşturur.
LIS algoritması ne kadar hızlıdır?
Tablo yöntemi her konum çiftini karşılaştırır: n değer için n·(n − 1)/2 karşılaştırma. Sabır sıralaması bunu O(n log n) sürede yapar: her uzunluk için o uzunlukta bir diziyi bitiren en küçük değeri tutar ve her yeni değeri ikili aramayla yerleştirir.
En uzun artan alt dizi tek midir?
Her zaman değil. 1, 3, 2, 4 listesinde hem 1, 3, 4 hem de 1, 2, 4 dizisinin uzunluğu 3'tür. Tablo uzunluğu verir, geriye okuma ise bunlardan birini bulur.
En uzun artan alt dizi nerede kullanılır?
Dosyaları ve genomları karşılaştırırken kullanılır: bazı yöntemler önce eşleşen satırları bulur, sonra bunların konumlarından artan bir alt dizi seçer. Planlama ve kutu üst üste dizme bulmacalarında da kullanılır. Matematikte ise rastgele karıştırılmış bir listenin LIS uzunluğu ünlü bir araştırma konusudur.
Herhangi bir veri bir yere gönderiliyor mu?
Hayır. Her şey tarayıcınızda hesaplanır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git