En uzun artan alt dizi (LIS)

Bir listeden soldan sağa, her biri bir öncekinden büyük olacak şekilde sayılar seçin. Böyle bir zincir ne kadar uzun olabilir? Soru bir bulmaca kitabına girecek kadar basittir; cevabı ise bir kart oyununu, klasik bir dinamik programlama tablosunu ve rastgele karıştırmalarla ilgili en güzel sonuçlardan birini birbirine bağlar.

Farklı yükseklikte çubuklardan oluşan bir sıra; soldan sağa yükselen bir çubuk zinciri turuncuyla vurgulanmış
Farklı yükseklikte çubuklardan oluşan bir sıra; soldan sağa yükselen bir çubuk zinciri turuncuyla vurgulanmış

Problem

Bir sayı listesi verildiğinde, bir alt dizi bu sayıların bazılarını özgün sıralarıyla tutar. Her değer bir öncekinden büyükse alt dizi artandır. En uzun artan alt dizi (LIS), böyle bir seçimin en uzunudur. n değerli bir listenin 2ⁿ alt dizisi vardır, bu yüzden hepsini denemek yalnızca çok kısa listelerde işe yarar.

Tablo

len[i], tam olarak i konumunda biten en uzun artan alt dizinin uzunluğu olsun. Bu değer, yalnızca o değer için 1 ya da değeri daha küçük olan önceki bir j konumu için 1 + len[j] olur; hangisi en büyükse o seçilir. Her konum önceki tüm konumlara baktığı için tablo n·(n − 1)/2 karşılaştırma gerektirir. Cevap en büyük len[i] değeridir; her len[i] değerini hangi j'nin verdiğini not etmek, alt diziyi geriye doğru okumayı sağlar.

Bir örnek

3, 10, 2, 1, 20, 4, 6, 7, 5, 9 listesini alın. Konum konum uzunluklar 1, 2, 1, 1, 3, 2, 3, 4, 3 ve 5'tir: 20 sayısı 3, 10 dizisini uzatır; 4 sayısı 3'ü, 6 sayısı 4'ü, 7 sayısı 6'yı ve 9 sayısı 7'yi uzatır. 9'dan geriye doğru okumak 3, 4, 6, 7, 9 dizisini verir: uzunluğu 5 olan artan bir alt dizi.

Daha hızlı bir yol: sabır sıralaması

Değerleri kart dağıtır gibi destelere dağıtın: her değer, en üstteki kartı kendisinden küçük olmayan en soldaki desteye konur ya da sağda yeni bir deste başlatır. Deste sayısı LIS'in uzunluğudur. Destelerin en üstteki kartları her zaman sıralı olduğu için doğru deste ikili aramayla bulunabilir; böylece yöntemin tamamı O(n log n) adım sürer. Adını, benzediği pasiyans (sabır) kart oyunundan alır.

Biraz matematik

1935'te Paul Erdős ve George Szekeres, n² + 1 farklı sayıdan oluşan her listede n + 1 uzunluğunda artan ya da azalan bir alt dizi bulunduğunu kanıtladı. Stanislaw Ulam 1961'de, n sayının rastgele karıştırılmasıyla elde edilen listenin LIS'inin ne kadar uzun olduğunu sordu. Büyük n için 2√n'ye yakın olan cevap 1977'de Anatoly Vershik ile Sergei Kerov ve Ben Logan ile Larry Shepp tarafından kesinleştirildi; 1999'da da Jinho Baik, Percy Deift ve Kurt Johansson dalgalanmalarının tam biçimini buldu: rastgele matris kuramından Tracy–Widom dağılımı.

1992’de Budapeşte’de bir öğrenci seminerinde Paul Erdős. 1935’te George Szekeres ile birlikte, n² + 1 farklı sayıdan oluşan her listenin n + 1 uzunluğunda artan ya da azalan bir alt dizisi olduğunu kanıtladı.
1992’de Budapeşte’de bir öğrenci seminerinde Paul Erdős. 1935’te George Szekeres ile birlikte, n² + 1 farklı sayıdan oluşan her listenin n + 1 uzunluğunda artan ya da azalan bir alt dizisi olduğunu kanıtladı.
Stanisław Ulam'ın portresi
Stanisław Ulam'ın portresi

Keşfedin

Uygulamayı açın ve Adım'a basın. Turuncu sütun hesaplanan konum, mavi sütun ise onunla karşılaştırılan önceki konumdur. Daha uzun diziler bulundukça Uzunluk satırı büyür, Ardından geldiği satırı bu dizilerin nereden geldiğini hatırlar ve sonunda cevap turuncuyla geriye doğru okunup tablonun altında gösterilir.

Sık sorulan sorular

LIS'in zaman karmaşıklığı nedir?

Tabloyla O(n²), çünkü her konum önceki her konuma bakar; sabır sıralaması ve ikili aramayla O(n log n). İkisi de O(n) bellek gerektirir.

En uzun azalmayan alt diziyi nasıl bulurum?

Bir değerin kendisine eşit bir değerin ardından gelmesine izin verin: < yerine ≤ ile karşılaştırın. Uygulamada Eşit değerlere izin ver kutusunu işaretleyin. Sabır sıralamasında her değeri, en üstteki kartı ondan kesinlikle büyük olan en soldaki desteye koyun.

En uzun azalan alt dizi nedir?

Karşılaştırması tersine çevrilmiş aynı problemdir; ya da her değerin işareti değiştirilmiş listenin LIS'idir. Erdős–Szekeres teoremine göre yeterince uzun bir listede her zaman uzun bir artan ya da uzun bir azalan alt dizi vardır.

Rastgele bir listenin LIS'i ne kadar uzundur?

n farklı sayının rastgele karıştırılmasında, büyük n için 2√n'ye yakındır. Düzeltme n'nin altıncı kökü gibi büyür; bu yüzden bin sayı için ortalama yaklaşık 58'dir, yani 2√1000 ≈ 63'ün biraz altında.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

En uzun artan alt diziyi deneyin