En uzun artan alt dizi

Problem

Bir tamsayı dizisi veriliyor. Elemanların bir kısmını silerek (kalanların sırasını bozmadan) elde edilen ve kesin artan olan en uzun alt dizinin uzunluğunu döndür. Alt dizinin elemanları orijinalde yan yana olmak zorunda değildir.

[3, 10, 2, 1, 20, 4, 6, 7]
En uzun artan alt dizi: 2, 4, 6, 7  (ya da 1, 4, 6, 7)
Çıktı: 4

[5, 5, 5]   -> 1   (kesin artan: eşitler sayılmaz)
[]          -> 0

Netleştirme soruları

• Kesin artan mı, azalmayan mı? (Kesin artan. Azalmayan olsaydı binary search'te lowerBound yerine upperBound kullanılırdı.)
• Uzunluk mu, alt dizinin kendisi mi isteniyor?
• Dizi uzunluğu ne kadar? (n = 2.500 ise O(n²) yeter; n = 10^5 ise O(n log n) gerekir.)
• Boş dizi olabilir mi? Değer aralığı?

İpuçları

Yaklaşım

Kaba çözüm: Tüm 2ⁿ alt diziyi üret, artan olanların en uzununu bul: O(2ⁿ · n).

O(n²) DP: dp[i] = 1 + max(dp[j]), j < i ve nums[j] < nums[i] olan tüm j'ler için (yoksa 1). Cevap max(dp). Durum tanımındaki "i'de biten" kısmı kritiktir: "ilk i eleman içindeki en uzun" diye tanımlarsan son elemanı bilmediğin için geçiş kurulamaz. Testlerde referans olarak bu çözüm kullanıldı.

O(n log n): tails + binary search (seçilen çözüm). tails[L-1], uzunluğu L olan artan alt diziler arasında en küçük son elemandır. İki özellik:

1. tails kesin artandır. (Uzunluğu L + 1 olan bir alt dizinin son elemanı, ondan önceki L uzunluklu önekinin son elemanından büyüktür; dolayısıyla L uzunluklu en küçük son eleman daha küçüktür.)
2. Yeni x için, x'ten büyük-eşit ilk tails[pos]'u x ile değiştirmek tüm değerleri doğru tutar: x, tails[pos-1]'den büyük olduğu için uzunluğu pos + 1 olan bir alt diziyi bitirebilir ve mevcut sondan küçük ya da eşittir. pos == length ise x tüm sonlardan büyüktür ve en uzun alt diziyi uzatır.

Önemli tuzak: tails dizisinin kendisi geçerli bir artan alt dizi değildir; sadece uzunluğu doğrudur. [3, 10, 2] sonunda tails = [2, 10] olur, ama 2, 10 sırası orijinalde yoktur. Alt diziyi geri kurmak için her elemanın öncülünü ayrıca tutmak gerekir.

Bu algoritma "patience sorting" (sabır oyunu) kart oyunundan gelir: her kart, üstü kendisinden büyük-eşit olan en soldaki desteye konur; deste sayısı LIS uzunluğudur.

Java çözümü

public final class LongestIncreasingSubsequence {

    public int lengthOfLIS(int[] nums) {
        // tails[i]: uzunluğu i+1 olan artan alt dizilerin en küçük olası son elemanı (artan sıralı)
        int[] tails = new int[nums.length];
        int length = 0;
        for (int x : nums) {
            int pos = lowerBound(tails, length, x);       // x'ten büyük-eşit ilk tail
            tails[pos] = x;                               // ya mevcut uzunluğun sonunu küçült ya da uzat
            if (pos == length) length++;
        }
        return length;
    }

    /** [0, size) içinde target'tan büyük ya da eşit ilk indeks. */
    private int lowerBound(int[] sorted, int size, int target) {
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (sorted[mid] < target) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
}

lowerBound (büyük-eşit ilk konum) kesin artan alt dizi için doğru seçimdir: eşit bir eleman geldiğinde yeni bir uzunluk açmaz, aynı sonun yerine yazılır. Arrays.binarySearch da kullanılabilir (bulunamazsa -(insertionPoint) - 1 döner), ama tekrarlı elemanlarda hangi indeksi döndüreceği garanti değildir; kendi lowerBound'unu yazmak daha güvenlidir. lo + (hi - lo) / 2 ifadesi (lo + hi) / 2'nin taşma riskini ortadan kaldırır.

Karmaşıklık

• Zaman: O(n log n); her eleman için bir binary search.
• Bellek: O(n) tails dizisi.
• O(n²) DP: O(n²) zaman, O(n) bellek.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• [3, 10, 2, 1, 20, 4, 6, 7]: 4.
• [5, 5, 5]: 1 (eşitler kesin artan değil). upperBound kullanan hatalı bir versiyon burada 3 döner.
• Boş dizi: 0; tek eleman: 1; azalan dizi: 1.
• [MIN, 0, MAX]: 3 (uç değerler).
• 3.000 rastgele dizi (uzunluk 0-24, değerler -5..9, bol tekrarlı) O(n²) DP referansıyla karşılaştırıldı.

Mülakatçı için

Çoğu aday O(n²) DP'yi yazar; bu orta seviye için yeterli bir cevaptır. O(n log n) çözüm, senior ya da güçlü bir sinyal arıyorsan sorulur. Asıl değerlendirme, adayın tails dizisinin anlamını açıklayabilmesidir; ezberden yazan aday "neden doğru?" sorusunda zorlanır ve genelde tails'i gerçek alt dizi sanır.

İpucu zamanlaması: O(n²) DP'nin durum tanımında takılan adaya (ör. "ilk i elemandaki en uzun") birinci ipucunu ver. O(n²) bitince "n = 10^5 olsa?" diye sor ve 5 dakika düşünmesine izin ver; ilerleme yoksa ikinci ipucu. Üçüncü ipucu çözümü neredeyse verir; bunu kullandıysan değerlendirmede not et.

Takip sorusu 1: Alt dizinin kendisini döndür. Beklenen: tailsIndex[L] (son elemanın orijinal indeksi) ve her eleman için prev[i] tutmak; sondan geri izlemek. O(n log n) kalır.

Takip sorusu 2: Zarfları iç içe koyma (Russian Doll Envelopes): her zarf (genişlik, yükseklik); en fazla kaç zarf iç içe girer? Beklenen: genişliğe göre artan, eşit genişlikte yüksekliğe göre azalan sırala, sonra yükseklikler üzerinde LIS (LeetCode 354). Azalan sıralama, aynı genişlikteki zarfların birbirinin içine girmesini engeller.

Takip sorusu 3: En uzun artan alt dizilerin sayısı. Beklenen: O(n²) DP'de length[i] ile birlikte count[i] tutmak (LeetCode 673).

Benzer problemler

• Russian Doll Envelopes (LeetCode 354)
• Number of Longest Increasing Subsequence (LeetCode 673)
• Increasing Triplet Subsequence (LeetCode 334)
• Longest Common Subsequence (LeetCode 1143)
• Maximum Length of Pair Chain (LeetCode 646)