Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumone-dimensional-dp

Longest Increasing Subsequence

Problem (yeniden ifade)

En uzun katı artan alt dizinin uzunluğunu döndür.

Sezgi

Her uzunluktaki artan alt dizilerin en küçük kuyruğunu tut; her sayı için yeri ikili aramayla bul.

Yaklaşımlar

Patience sorting (kuyruklar)

Tested only

Time O(n log n)Space O(n)

Fikir. tails[len-1] = uzunluk len için en küçük kuyruk; lower_bound ile değiştir veya ekle.

Adım adım. [10,9,2,5,3,7,101,18] → uzunluk 4 (2,3,7,101).

Trade-off’lar. O(n²) DP daha basit; patience daha hızlı.

Solution

export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x);
    else tails[lo] = x;
  }
  return tails.length;
}

export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x);
    else tails[lo] = x;
  }
  return tails.length;
}

Şablon bağlantısı

1D DP / cevap yapısı üzerinde ikili arama.

Yansıma

Hangi kalıp bunu 90 saniyede ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozardı?