Temu Duga Pengekodan: Bagaimana Anda Mencari Subjujukan Meningkat Terpanjang (Longest Increasing Subsequence)?

Masalah dan senario yang berkenaan

Diberikan satu tatasusunan integer nums, kembalikan mana-mana subjujukan meningkat secara ketat (strictly increasing) yang terpanjang. Subjujukan mengekalkan susunan relatif input tetapi tidak semestinya bersebelahan. "Meningkat secara ketat" bermakna setiap nilai seterusnya mestilah lebih besar, jadi nilai yang sama tidak boleh menambah panjang. Jika terdapat beberapa jawapan optimum, kembalikan mana-mana satu. Kembalikan tatasusunan kosong untuk input kosong.

Input:  [10, 9, 2, 5, 3, 7, 101, 18]
Output: [2, 3, 7, 18]

Increasing indices: 2 < 4 < 5 < 7
Increasing values:  2 < 3 < 7 < 18
Length: 4

Andaikan 0 ≤ n ≤ 100,000, nilai integer 32-bit bertanda, dan tatasusunan input yang mesti kekal tidak berubah. Skala ini menolak kaedah menyenaraikan semua subjujukan dan menolak pengaturcaraan dinamik (DP) kuadratik sebagai penyelesaian akhir. Masalah LeetCode meminta panjang bagi subjujukan meningkat secara ketat dan secara eksplisit menyusul dengan sasaran O(n log n). Sebuah artikel persediaan temu duga awam bertarikh April 2026 masih mengajar kedua-dua DP kuadratik dan pengoptimuman carian binari. Versi ini juga mengembalikan subjujukan sebenar. Sumber-sumber tersebut menetapkan masalah dan nilai persediaannya pada masa kini; ia tidak menetapkan kekerapan temu duga atau atribusi syarikat.

Perkara yang dinilai oleh penemu duga

Isyarat pertama ialah definisi keadaan (state) yang tepat. Penyelesaian kuadratik harus mentakrifkan dp[i] sebagai panjang terbaik yang mesti berakhir pada nums[i]. Sekadar menyatakan "jawapan untuk i nilai pertama" membuang nilai penamat yang diperlukan untuk memutuskan sama ada elemen semasa boleh disambungkan.

Isyarat kedua ialah menerbitkan pengoptimuman daripada kekangan prestasi (bottleneck). Mengimbas setiap j sebelumnya bagi setiap i menelan kos O(n²). Jawapan yang lebih kukuh menukar keadaannya: bagi setiap panjang yang boleh dicapai, simpan hanya nilai penamat terkecil. Hujung (tail) yang lebih kecil adalah sekurang-kurangnya sama mudah untuk disambung. Nilai-nilai minimum tail ini meningkat secara ketat, jadi kedudukan kemas kini boleh dicari menggunakan carian binari.

Isyarat ketiga ialah mengendalikan duplikasi dengan betul. Jujukan yang meningkat secara ketat memerlukan kedudukan pertama yang tail-nya lebih besar daripada atau sama dengan nilai semasa: semantik batas bawah (lower-bound). Nilai yang sama menggantikan kedudukan yang sama dan tidak memanjangkan jujukan. Hanya varian tidak menurun (non-decreasing) menggunakan kedudukan pertama yang strictly greater daripada nilai tersebut.

Isyarat keempat ialah mengetahui bahawa tails itu sendiri bukan jawapannya. Selepas [3, 5, 6, 2], nilai-nilai tail ialah [2, 5, 6]. Nilai-nilai tersebut meningkat mengikut nilai, tetapi indeks input asalnya ialah 3, 1, 2, jadi ia bukan satu subjujukan. Untuk mengembalikan laluan sebenar, simpan juga indeks input semasa bagi setiap panjang tail dan indeks pendahulu (predecessor) bagi setiap elemen.

Isyarat terakhir ialah pembuktian dan pengesahan. Calon harus menerangkan invariant minimum-tail, mengapa penggantian tidak akan kehilangan panjang optimum, mengapa pautan pendahulu membentuk laluan yang sah, dan bagaimana untuk membandingkan input kecil rawak terhadap oracle O(n²) dan bukannya bergantung pada satu contoh sahaja.

Soalan untuk dijelaskan sebelum menjawab

• Meningkat secara ketat (strictly increasing) atau tidak menurun (non-decreasing)? Masalah ini adalah ketat, jadi duplikasi tidak boleh memanjangkan jawapan. Jika kesamarataan dibenarkan, sempadan carian binari akan berubah.
• Kembalikan panjang atau jujukan sebenar? Masalah ini mengembalikan jujukan, jadi ia memerlukan previous dan indeks tail. Penyelesaian panjang sahaja boleh mengurangkan ruang bantuan kepada O(L), di mana L ialah panjang jawapan.
• Bagaimanakah keputusan seri antara jawapan optimum harus diselesaikan? Mana-mana jawapan boleh diterima. Keperluan untuk memilih susunan leksikografi terkecil, indeks terkecil, atau pemilihan yang stabil memerlukan peraturan dan bukti tambahan.
• Berapakah saiz input? Pada seratus ribu elemen, gunakan O(n log n). Untuk beberapa ratus elemen, DP kuadratik lebih mudah untuk dilaksanakan, diterangkan dan diperluas kepada pengiraan.
• Bolehkah input kosong? Ya; kembalikan []. Ini menentukan sama ada pembinaan semula boleh membaca indeks tail akhir.
• Bolehkah input diubah suai? Tidak. Menyusun (sorting) memusnahkan susunan indeks asal dan mengubah masalah.
• Bolehkah aritmetik integer melimpah (overflow)? Algoritma membandingkan dan menyalin nilai tanpa aritmetik ke atasnya, jadi input 32-bit bertanda tidak melimpah disebabkan oleh algoritma.

Rangka kerja jawapan 30 saat

"Saya mengekalkan tail terkecil untuk setiap panjang yang boleh dicapai. Tail tersebut disusun mengikut tertib, jadi untuk setiap nilai saya melakukan carian binari bagi mencari tail pertama yang lebih besar daripada atau sama dengannya, menggantikan kedudukan tersebut, atau menyambung di hujung. Batas bawah ini menghalang duplikasi daripada memanjangkan jujukan ketat. Tatasusunan tail mungkin mencampurkan indeks input yang tidak serasi, jadi saya juga menyimpan indeks bagi setiap tail dan pendahulu bagi setiap elemen, kemudian membina semula secara mengundur. Satu carian binari bagi setiap elemen memberikan masa O(n log n) dan ruang O(n). Saya menguji tatasusunan kosong, duplikasi, menurun, dan tatasusunan kecil rawak terhadap oracle kuadratik."

Penyelesaian mendalam langkah demi langkah

Mulakan dengan garis dasar yang paling mudah dibuktikan. Biarkan dp[i] menjadi panjang subjujukan meningkat secara ketat yang terpanjang yang mesti berakhir pada nums[i]. Mana-mana jawapan yang lebih panjang daripada satu mempunyai elemen kedua terakhir pada suatu j < i dengan nums[j] < nums[i]:

dp[i] = 1 + max(dp[j]) over j < i and nums[j] < nums[i]
If no such j exists, dp[i] = 1
Final length = max(dp[i])

Definisi ini juga membuktikan hubungan jadi semula (recurrence). Setiap pendahulu yang layak boleh disambung sebanyak nums[i], manakala setiap jujukan optimum yang berakhir pada nums[i] mesti beralih daripada salah satu pendahulu tersebut. Masalahnya ialah setiap i mengimbas semua kedudukan sebelumnya, menghasilkan jumlah masa O(n²).

Untuk pengoptimuman, kekalkan invariant awalan ini: selepas memproses i elemen pertama, tails[k] ialah nilai penamat terkecil yang mungkin dalam kalangan semua subjujukan meningkat secara ketat dengan panjang k + 1. Bagi nilai semasa x, cari kedudukan pertama yang memenuhi tails[k] ≥ x:

• Jika tiada kedudukan wujud, x melebihi setiap tail dan memanjangkan jujukan terpanjang sebanyak satu.
• Jika kedudukan k wujud, gantikan tails[k] dengan x. Panjangnya tidak berubah, tetapi tail yang lebih kecil atau sama tidak boleh mengurangkan pilihan sambungan pada masa hadapan.
• Disebabkan tails meningkat secara ketat, kedudukan tersebut ditemui dalam masa O(log L).

Untuk [3, 5, 6, 2], tiga keadaan pertama ialah [3], [3, 5], dan [3, 5, 6]. Nilai akhir 2 menggantikan kedudukan pertama, menghasilkan [2, 5, 6]. Panjangnya kekal betul, tetapi 2 berlaku selepas 5 dan 6 dalam input. Ini adalah contoh lawan (counterexample) kepada tindakan mengembalikan tails secara langsung.

Pembinaan semula memerlukan dua struktur indeks. tailsIndices[k] menyimpan kedudukan input yang sedang merealisasikan minimum tail untuk panjang k + 1. Apabila nums[i] berada pada kedudukan k, tetapkan previous[i] kepada tailsIndices[k - 1]. Pendahulu itu berlaku sebelum i dan mempunyai nilai yang lebih kecil secara ketat. Penggantian tail kemudiannya tidak mengubah pautan pendahulu yang telah ditulis. Bina semula secara mengundur daripada tail terpanjang terakhir.

export function longestIncreasingSubsequence(nums: number[]): number[] {
  if (nums.length === 0) return []

  const tails: number[] = []
  const tailsIndices: number[] = []
  const previous = new Array<number>(nums.length).fill(-1)

  for (let index = 0; index < nums.length; index += 1) {
    const value = nums[index]
    let left = 0
    let right = tails.length

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2)
      if (tails[middle] < value) left = middle + 1
      else right = middle
    }

    const lengthIndex = left
    if (lengthIndex > 0) {
      previous[index] = tailsIndices[lengthIndex - 1]
    }

    if (lengthIndex === tails.length) {
      tails.push(value)
      tailsIndices.push(index)
    } else {
      tails[lengthIndex] = value
      tailsIndices[lengthIndex] = index
    }
  }

  const result = new Array<number>(tails.length)
  let index = tailsIndices[tails.length - 1]

  for (
    let resultIndex = result.length - 1;
    resultIndex >= 0;
    resultIndex -= 1
  ) {
    result[resultIndex] = nums[index]
    index = previous[index]
  }

  return result
}

Ketepatan mempunyai tiga bahagian. Pertama, tails kekal meningkat secara ketat: mengalih keluar item terakhir daripada jujukan meningkat yang lebih panjang meninggalkan jujukan yang lebih pendek dengan tail yang lebih kecil. Kedua, penggantian carian binari mengekalkan tail terkecil yang boleh direalisasikan untuk setiap panjang; ia meningkatkan kebolehpanjangan tanpa mereka-reka jujukan yang lebih panjang. Ketiga, setiap tailsIndices[k] merealisasikan rantaian dengan panjang k + 1, dengan indeks pendahulu dan nilai yang meningkat secara ketat. Oleh itu tails.length tidak boleh melebihi optimum sebenar, dan mengimbas mana-mana LIS sebenar memaksa struktur mencapai sekurang-kurangnya panjang tersebut. Rantaian pendahulu yang dibina semula ialah jawapan optimum yang sah.

Setiap elemen melakukan satu carian binari ke atas paling banyak L tail, untuk masa O(n log L) dan batas atas konvensional O(n log n). Ketiga-tiga tatasusunan menggunakan ruang O(n); output itu sendiri menggunakan O(L). Algoritma tidak menyusun input mahupun bergantung pada julat berangka.

Ujian harus memeriksa panjang, peningkatan secara ketat, dan susunan indeks input:

const cases: Array<[number[], number]> = [
  [[10, 9, 2, 5, 3, 7, 101, 18], 4],
  [[0, 1, 0, 3, 2, 3], 4],
  [[7, 7, 7, 7], 1],
  [[5, 4, 3, 2, 1], 1],
  [[], 0],
]

for (const [nums, expectedLength] of cases) {
  const result = longestIncreasingSubsequence(nums)
  if (result.length !== expectedLength) throw new Error("wrong length")
  for (let i = 1; i < result.length; i += 1) {
    if (result[i - 1] >= result[i]) throw new Error("not increasing")
  }
}

Pemeriksaan yang lebih kukuh menjana tatasusunan rawak dengan panjang paling banyak 12 dan membandingkan panjang hasil yang dioptimumkan dengan oracle DP O(n²). Imbasan linear melalui input juga harus mengesahkan bahawa nilai yang dikembalikan muncul mengikut susunan. Secara bersama, pemeriksaan ini mendedahkan ralat sempadan duplikasi, syarat carian binari yang salah, dan pendahulu yang rosak.

Contoh jawapan berkualiti tinggi

"Saya akan mengesahkan terlebih dahulu bahawa susunan adalah ketat dan saya mesti mengembalikan jujukan sebenar. Penyelesaian kuadratik mentakrifkan dp[i] sebagai panjang terbaik yang berakhir pada nums[i] dan menyemak setiap pendahulu yang lebih kecil. Untuk menghapuskan imbasan ke belakang itu, saya menyimpan tail terkecil yang mungkin bagi setiap panjang.

Bagi nilai x, saya mencari tail pertama yang lebih besar daripada atau sama dengan x. Jika tiada, x memanjangkan jujukan terpanjang semasa. Jika ada, menggantikan tail tersebut dengan x memberikan panjang yang sama nilai yang sekurang-kurangnya sama mudah untuk disambung. Peningkatan secara ketat memerlukan kedudukan lower-bound ini, jadi duplikasi menggantikan nilai dan bukannya memanjangkan jujukan.

Nilai tail meringkaskan penamat terbaik bagi setiap panjang; ia tidak semestinya datang daripada indeks input yang serasi. Untuk mengembalikan jawapan sebenar, tailsIndices[k] merekodkan indeks tail semasa untuk panjang k + 1. Apabila elemen berada pada kedudukan k, pendahulunya ialah tailsIndices[k - 1]. Selepas imbasan, saya mengikut pendahulu daripada tail terpanjang dan mengisi output secara mengundur.

Invariantnya ialah setiap tail adalah tail terkecil yang boleh direalisasikan untuk panjangnya, dan setiap indeks tail mempunyai rantaian pendahulu yang sebenar. Penggantian tidak pernah membuang panjang sedia ada dan hanya menambah baik sambungan masa hadapan. Sebaliknya, mengimbas setiap elemen bagi mana-mana subjujukan meningkat yang sebenar memaksa struktur mencapai sekurang-kurangnya panjang tersebut, jadi panjang akhir adalah optimum. Satu carian binari bagi setiap elemen memberikan masa O(n log n), dan indeks serta pendahulu menggunakan ruang O(n). Saya akan menguji input kosong, duplikasi, meningkat, dan menurun, kemudian membandingkan tatasusunan kecil rawak dengan oracle kuadratik."

Kesilapan biasa

• Menganggap subjujukan sebagai subtatasusunan bersebelahan (contiguous) → Tetingkap gelongsor (sliding window) tidak boleh melangkau elemen → Takrifkan jawapan mengikut indeks input yang meningkat.
• Menyusun sebelum menyelesaikan → Menyusun memusnahkan susunan relatif asal → Proses nilai mengikut susunan input.
• Mentakrifkan dp[i] sebagai optimum awalan dan beralih secara langsung → Tail bagi nilai optimum mungkin tidak menerima nilai semasa → Wajibkan keadaan berakhir pada i.
• Mencari tail pertama yang strictly greater daripada nilai dalam varian ketat → Duplikasi memanjangkan panjang secara salah → Cari tail pertama yang lebih besar daripada atau sama dengan nilai tersebut.
• Mengembalikan tails secara langsung → Nilai tail mungkin datang daripada indeks input yang menurun → Bina semula dengan indeks tail dan pautan pendahulu.
• Menulis semula pendahulu lama selepas penggantian tail → Laluan yang sah sebelum ini dirosakkan → Kekalkan setiap pendahulu tidak boleh diubah (immutable) selepas penugasan.
• Hanya membuktikan bahawa tail disusun → Keteraturan susunan sahaja tidak membuktikan panjang optimum → Buktikan invariant minimum realizable tail dan kedua-dua batas panjang.
• Memanggil carian binari ditambah penyisipan tatasusunan sebagai O(log n) → Penyisipan di tengah menggeser elemen → Hanya ganti di tempat asal (in-place) atau sambung di hujung.
• Hanya menjalankan contoh klasik → Pepijat duplikasi dan pendahulu kekal tersembunyi → Gunakan ujian oracle untuk semua-sama, menurun, kosong dan rawak.
• Mendakwa kekerapan tinggi di syarikat yang dinamakan → Halaman masalah awam tidak membuktikan kekerapan atau atribusi → Nyatakan hanya masalah yang disahkan dan nilai algoritma.

Soalan susulan dan respons

Soalan Susulan 1: Apakah yang berubah untuk longest non-decreasing subsequence?

Nilai yang sama kini boleh memanjangkan jujukan. Tukar sempadan kepada kedudukan pertama yang strictly greater daripada value, iaitu titik penyisipan kanan. Pendahulu, pembinaan semula, dan kerumitan kekal sama. Menukar perbandingan akhir sahaja tanpa menukar sempadan carian binari akan gagal pada duplikasi.

Soalan Susulan 2: Bolehkah jawapan panjang sahaja menggunakan ruang yang lebih sedikit?

Ya. Buang tailsIndices dan previous, dan kekalkan hanya L nilai minimum tail untuk ruang O(L). Masa kekal O(n log L). Mengembalikan jujukan sememangnya memerlukan output O(L), manakala pembinaan semula satu laluan ini menggunakan maklumat pendahulu bagi setiap kedudukan input.

Soalan Susulan 3: Bagaimana anda mengira bilangan longest increasing subsequence?

Minimum tails menggabungkan berbilang laluan dengan panjang yang sama, jadi ia tidak dapat memulihkan kiraan secara langsung. Penyelesaian mudah mengekalkan length[i] dan count[i]: salin kiraan pendahulu apabila laluan yang lebih panjang ditemui dan tambah kiraan apabila laluan dengan panjang yang sama ditemui, untuk masa O(n²). Input yang lebih besar boleh memampatkan koordinat nilai (coordinate compression) dan menggunakan Fenwick tree atau segment tree yang menyimpan pasangan panjang-maksimum-dan-kiraan, dengan peraturan gabungan yang berhati-hati untuk mengelakkan pengiraan berganda.

Soalan Susulan 4: Bagaimana jika nilai tiba dalam penstriman append-only?

Panjang LIS semasa adalah dalam talian (online): lakukan carian binari pada tails untuk setiap nilai yang tiba dalam masa O(log L). Kekalkan indeks dan pendahulu jika jujukan sebenar mesti disediakan. Jika nilai lama boleh dipadamkan, minimum tail mungkin bergantung pada data yang dipadamkan; algoritma ini tidak boleh membatalkan keadaan tersebut secara tempatan, jadi struktur dinamik atau penguraian luar talian diperlukan.

Soalan Susulan 5: Bagaimana jika setiap elemen mempunyai pemberat dan matlamatnya adalah jumlah pemberat maksimum?

Minimum tail tidak lagi meringkaskan keadaan kerana julat tail yang sama boleh membawa pemberat terkumpul yang berbeza. Mampatkan koordinat nilai, buat pertanyaan pada Fenwick tree atau segment tree untuk mencari pemberat terbaik dalam kalangan nilai yang lebih kecil, tambah pemberat semasa, dan kemas kini koordinat semasa. Varian ketat dan tidak menurun masih menggunakan sempadan pertanyaan yang berbeza. Masanya ialah O(n log n).

Soalan Susulan 6: Adakah kod ini mengembalikan jawapan optimum yang terkecil dari segi leksikografi?

Ia tidak menjamin perkara itu. Peraturan penggantian meminimumkan nilai tail individu tetapi tidak mentakrifkan susunan stabil antara laluan optimum yang lengkap. Satu pendekatan mengira berapa banyak awalan atau akhiran optimum yang boleh disokong oleh setiap indeks, kemudian memilih nilai secara tamak (greedily) yang masih boleh melengkapkan jawapan panjang optimum. Jujukan nilai terkecil dan jujukan indeks terkecil adalah keperluan yang berbeza, jadi jelaskan susunan leksikografi mana yang dimaksudkan terlebih dahulu.