Longest Increasing Subsequence

Listeyi baştan sona gözden geçir ve her öğe için bir karar ver: tut ya da dışarıda bırak. nums[i] öğesini yalnızca tuttuğun son değerden büyükse tutabilirsin. Özyinelemeli longest(i, prev) fonksiyonu şu soruyu yanıtlar: Tutulan son öğe prev indeksindeyse (ya da henüz hiçbir şey tutulmadığında -1 ise), i indeksinden itibaren kaç öğe daha ekleyebilirsin?

Atlamak longest(i+1, prev) sonucunu verir. İzin verildiğinde tutmak ise 1 + longest(i+1, i) sonucunu verir. Yanıt bu ikisinden büyük olanıdır; listenin sonuna gelindiğinde artık başka bir şey eklenemeyeceğinden sonuç 0 olur. Her artan alt dizi, tutma ve atlama seçimlerinden oluşan bir yoldur; bu nedenle arama en iyisini kaçırmaz.

Değerler arttığında her iki dal da açık kaldığı için bu yöntem yavaştır. 1, 2, 3, ..., n gibi bir listede çağrı sayısı her öğeyle ikiye katlanır: 2 üzeri 40, şimdiden yaklaşık 10^12 çağrı demektir ve büyük testlerde 2500 öğe bulunur. Ancak longest(i, prev) yalnızca (i, prev) çiftine bağlıdır; dolayısıyla en fazla n² farklı soru vardır. Her soruyu bir kez sormak, sıradaki yaklaşımdır.

Durum. ending[i], son elemanı nums[i] olan en uzun artan alt dizinin uzunluğu olsun. Son elemanı sabitlemek, problemi düzgün bir şekilde parçalara ayırmayı sağlar: Bir alt dizinin nerede bittiğini bildiğinde, onu hangi sonraki değerlerin izleyebileceğini bilirsin.

Özyineleme bağıntısı. nums[i] noktasında biten alt dizide birden fazla eleman varsa, nums[i] değerinden önceki eleman, j < i ve nums[j] < nums[i] koşullarını sağlayan bir nums[j] değeridir ve bu elemana kadarki kısım mümkün olduğunca uzun olmalıdır. Dolayısıyla ending[i] = 1 + max(ending[j]); burada j bu koşulları sağlayan indekslerdir. Temel durum: Her eleman tek başına bir alt dizi olduğundan ending[i] başlangıçta 1 olur. Sıra: ending[i] yalnızca daha küçük indeksleri okur, bu yüzden soldan sağa doldur.

[3, 1, 8, 2, 5, 9, 4, 7] için tablo [1, 1, 2, 2, 3, 4, 3, 4] olur. Örneğin 5, 3'ün, 1'in veya 2'nin ardından gelebilir ve bunların en iyisi ending = 2 olan 2'dir; dolayısıyla ending[4] = 3 olur. Yanıt en büyük değer olan 4'tür, son değer değil: en iyi alt dizi herhangi bir yerde bitebilir.

Her indeks, kendisinden önceki her indekse bir kez bakar; dolayısıyla işlem sayısı n(n-1)/2 karşılaştırmadır. n = 2500 için bu yaklaşık 3.1 × 10^6 karşılaştırma eder.

Yukarıdaki tablo, her indeks için bir uzunluk saklar. Daha azını saklayabilirsin: her uzunluk için, o uzunluktaki artan bir alt dizinin bitebileceği en küçük değeri sakla. Uzunluk k+1 için buna tails[k] adını ver. Daha küçük bir bitiş değeri her zaman en az onun kadar iyidir; çünkü 9 ile biten bir alt diziyi izleyebilen herhangi bir değer, 5 ile biten bir alt diziyi de izleyebilir.

tails her zaman kesin artan sıradadır: t ile biten, k+2 uzunluğundaki bir alt dizi, t'den küçük bir değerle biten k+1 uzunluğunda bir alt dizi içerir. Bu yüzden her yeni x değeri için, ≥ x olan ilk kuyruğu ikili aramayla bul. Böyle bir kuyruk yoksa x tüm kuyruklardan büyüktür ve en uzun alt diziyi uzatır; bu nedenle sona ekle. Aksi takdirde o kuyruğu x ile değiştir: bir eleman daha kısa olan alt dizi x'ten küçük bir değerle biter; dolayısıyla x'i eklemek, daha küçük bir bitiş değeriyle aynı uzunluğu verir.

[3, 1, 8, 2, 5, 9, 4, 7] için tails sırasıyla [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7] olur ve uzunluğu 4 olan cevap budur. [1, 2, 4, 9] adımında 4, girdide 9'dan sonra geldiği için tails kendi başına bir alt dizi değildir; yalnızca uzunluğunun bir anlamı vardır. Bu yönteme, her kuyruğun bir yığının en üst kartı olduğu kart oyunundan esinlenerek sabır sıralaması da denir.

Her eleman, en fazla n kuyruk üzerinde bir ikili arama gerektirir: en büyük girdi için yaklaşık 2500 × 12 = 30,000 adım.