Longest Increasing Subsequence
Bir tamsayı listesi nums alıyorsunuz. Bir alt dizi, bazı öğeleri özgün sıralarında tutar ve geri kalanları çıkarır; tutulan öğelerin yan yana olması gerekmez. Değerleri soldan sağa doğru kesin olarak artan en uzun alt dizinin uzunluğunu döndürün. Art arda gelen iki eşit değer artış sayılmaz.
Fonksiyon
- numsinteger-array
- seçilecek tam sayıların listesi
- Döndürürinteger
- en uzun kesin artan alt dizinin uzunluğu
Kısıtlar
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
Örnekler
- Girdi
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- Çıktı
- 4
- Açıklama
- 1, 2, 5, 9 artıyor; 1, 2, 5, 7 ve 1, 2, 4, 7 de öyle: uzunluk 4. Beş değerlik hiçbir seçim artmaya devam etmiyor.
- Girdi
- nums = [7, 7, 7, 7]
- Çıktı
- 1
- Açıklama
- Değerler kesinlikle artmalıdır; bu nedenle iki 7 aynı alt dizide bulunamaz. Tek bir eleman da sayılır, bu yüzden cevap 1'dir.
- Girdi
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- Çıktı
- 4
- Açıklama
- -4, 0, 3, 16 uzunluğu 4'tür. İlk öğe olan 12'den başlayınca yalnızca 12, 25 gibi iki değer elde edersin: en iyi alt dizinin baştan başlaması gerekmez.
Ek soru
Uzunluğu ile birlikte, en uzun artan alt dizinin kendisini de döndürebilir ve yine O(n log n) zamanda çalışabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Tüm listenin en iyi alt dizisini doğrudan tanımlamak zordur. Her
iindeksi için daha dar bir soru sorun: Tam olaraknums[i]ile biten en uzun artan alt dizi nedir?nums[i]ile biten bir alt dizi ya yalnızcanums[i]değerinden oluşur ya da daha önceki birnums[j] < nums[i]değerinde biten en iyi alt diziyi sürdürür. Bu türjdeğerleri arasından en iyisini seçip bir ekleyin. Cevap, nerede biterse bitsin, bu değerlerin en büyüğüdür.O(n²)'nin altına inmek için her uzunluk için, o uzunluktaki bir alt dizinin bitebileceği en küçük değeri tut. Bu değerler sıralı kalır; dolayısıyla ikili arama, yeni bir sayının en uzun diziyi uzatıp uzatmadığını veya bir bitiş değerinin yerine geçip geçmediğini söyler.
Çözüm
n sayıdan oluşan bir listenin 2^n alt dizisi vardır; bunların hepsini kontrol etmek çok fazla zaman alır. Her indeks için, tam olarak orada biten en iyi artan alt dizinin uzunluğunu sormak O(n²) boyutunda bir tablo verir. En hızlı sürüm, her uzunluk için o uzunluktaki bir alt dizinin bitebileceği en küçük değeri tutar ve her öğeyi ikili aramayla yerleştirir.
Her öğeyi al veya atla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her öğe için onu tutup tutmayacağına karar ver; nums[i] öğesini yalnızca tutulan son değerden büyük olduğunda tutabilirsin. longest(i, prev), tutulan son öğe prev konumundayken (veya -1 değerindeyken) i indeksinden itibaren ekleyebileceğin en fazla öğe sayısıdır. Atlamak longest(i+1, prev) sonucunu verir; tutmak ise 1 + longest(i+1, i) sonucunu verir. Her artan alt dizi, bu seçimlerin izlediği yollardan biridir.
1, 2, 3, ..., n dizisinde her iki dal da açık kalır ve çağrı sayısı her öğeyle birlikte ikiye katlanır: 2^40 şimdiden yaklaşık 10^12 eder. Ancak en fazla n² farklı (i, prev) çifti vardır.
Algoritma
longest(i, prev)fonksiyonunu yaz; buradaprev, tutulan son elemanın indeksidir veya-1değeridir.idizinin sonunu geçtiyse 0 döndür.nums[i]değerini atla:best = longest(i+1, prev).prevdeğeri-1ise veyanums[i] > nums[prev]koşulu sağlanıyorsa, bu elemanı tut:best = max(best, 1 + longest(i+1, i)).bestdeğerini döndür. Cevaplongest(0, -1)olur.
def lengthOfLIS(nums):
def longest(i, prev):
# The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
# prev is -1 while nothing has been taken.
if i == len(nums):
return 0
best = longest(i + 1, prev) # skip nums[i]
if prev == -1 or nums[i] > nums[prev]:
best = max(best, 1 + longest(i + 1, i)) # take nums[i]
return best
return longest(0, -1)Her indekste sona eren en uzun alt dizi
Sezgi
ending[i], son elemanı nums[i] olan en uzun artan alt dizinin uzunluğu olsun. Varsa nums[i] öğesinden önce gelen öğe, j < i ve nums[j] < nums[i] koşullarını sağlayan bir nums[j] değeridir ve bu öğeye kadarki bölüm mümkün olduğunca uzun olmalıdır. Dolayısıyla ending[i] = 1 + max(ending[j]) eşitliği, bu j değerleri için geçerlidir; hiçbiri yoksa sonuç 1 olur. Değerleri soldan sağa doldur.
[3, 1, 8, 2, 5, 9, 4, 7] için tablo [1, 1, 2, 2, 3, 4, 3, 4] olur: 5, 3'ün, 1'in veya 2'nin ardından gelebilir ve bunların en iyisinin uzunluğu 2'dir; bu nedenle ending[4] = 3. En uzun alt dizi herhangi bir yerde bitebileceğinden yanıt, en büyük değerdir.
n(n-1)/2 karşılaştırma: n = 2500 için yaklaşık 3.1 × 10^6.
Algoritma
- Her girdisi 1 olacak şekilde
endingoluşturun. - Soldan sağa her
iiçin, tümj < ideğerlerine bakın. nums[j] < nums[i]ise ve bu değer daha büyükse,ending[i]değeriniending[j] + 1olarak ayarlayın.endingiçindeki en büyük değeri döndürün.
def lengthOfLIS(nums):
n = len(nums)
# ending[i]: the longest increasing subsequence that ends with nums[i]
ending = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
ending[i] = ending[j] + 1
return max(ending)İkili aramayla en küçük kuyruklar
Sezgi
Her uzunluk için, o uzunluktaki artan bir alt dizinin bitebileceği en küçük değeri tut: uzunluk k+1 için tails[k]. Daha küçük bir bitiş değeri asla daha kötü değildir: 9'dan sonra gelebilecek her şey 5'ten sonra da gelebilir. tails kesin artan kalır: uzunluğu k+2 olan artan bir alt dizinin son değerini çıkarırsan, daha düşük bir değerle biten ve uzunluğu k+1 olan bir alt dizi elde edersin.
Her x için ilk kuyruk ≥ x değerini ikili aramayla bul. Böyle bir değer yoksa x'i sona ekle: bu, en uzun diziyi genişletir. Aksi hâlde o kuyruğu x ile değiştir: bir kısa alt dizi x'ten daha düşük bir değerle biter; dolayısıyla x, aynı uzunluğu daha küçük bir bitiş değeriyle sağlar.
Örneğin 1 için tails şu hâle gelir: [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: uzunluk 4. [1, 2, 4, 9] dizisinde 4, 9'dan sonra geldi; bu nedenle yalnızca tails'in uzunluğu anlamlıdır.
Algoritma
- Boş bir
tailslistesiyle başla. numsiçindeki herxiçin,tails[k] ≥ xkoşulunu sağlayan ilkkindeksini ikili aramayla bul.- Hiçbir kuyruk
≥ xdeğilsexdeğerini sona ekle. - Aksi hâlde
tails[k] = xolarak ayarla. tailslistesinin uzunluğunu döndür.
from bisect import bisect_left
def lengthOfLIS(nums):
# tails[k]: the smallest last value of any increasing subsequence of length k + 1
tails = []
for x in nums:
k = bisect_left(tails, x) # the first tail that is >= x
if k == len(tails):
tails.append(x) # x extends the longest subsequence so far
else:
tails[k] = x # x is a smaller ending for length k + 1
return len(tails)
Tuzaklar ve uç durumlar
- En büyük öğe yerine
ending[n-1]değerini döndürmek.[1, 2, 3, 0]için son öğe 1'dir, ancak yanıt 3'tür. <yerine≤ile karşılaştırmak.[7, 7, 7, 7]için 4 değil, 1 döndürülmelidir.- tails sürümünde, ilk
≥ xkuyruğu yerine ilk> xkuyruğunu aramak. Böylece ikinci 7 ilkinden sonra eklenir ve eşit değerler artıyor sayılır. - Yanlışlıkla bitişik sürümü çözmek. Örnek 1'de komşulardan oluşan en uzun artan dizi 2, 5, 9'dur (uzunluğu 3), yanıt ise 4'tür.
- Dizilerin 1'den başladığı Lua veya R'de 0 tabanlı dizinleri kullanmaya devam etmek.
prev = -1işareti 0 olur ve ikili arama, 1 ile geçerli boyut arasındaki dizinlerde çalışır.
Sıkça sorulan sorular3
En Uzun Artan Alt Dizi'nin zaman karmaşıklığı nedir?
tails yöntemi O(n log n) zamanda ve O(n) alan kullanarak çalışır: her öğe için bir ikili arama. Her indeks çifti üzerindeki tablo O(n²) zaman alır ve her alt diziyi denemek O(2ⁿ) zaman alır.
En Uzun Artan Alt Dizi probleminde sabır sıralaması nedir?
Adını bir kart oyunundan alan tails yöntemidir. Her kuyruk, bir yığının en üstündeki karttır: bir kart, en üstteki kartın değeri kendi değerine eşit ya da daha büyük olan en soldaki yığına konur veya yeni bir yığın başlatır. Yığınların sayısı cevaptır.
Bunun yerine en uzun azalmayan alt diziyi nasıl bulursunuz?
Eşit komşulara izin verin. Tabloda nums[j] ≤ nums[i] kullanın. tails yönteminde, x'ten kesinlikle büyük olan ilk kuyruğu arayın; böylece eşit bir değer kuyruğu değiştirmek yerine listeyi uzatır. [7, 7, 7, 7] bu durumda 4 döndürür.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def lengthOfLIS(nums):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
nums = [3, 1, 8, 2, 5, 9, 4, 7]
Beklenen Çıktı
4