Meditasi LeetCode: Susunan Bertambah Terpanjang

Penerangan untuk masalah ini hanya menyatakan:

Memandangkan nombor tatasusunan integer, kembalikan panjang terpanjang urutan yang semakin meningkat.

Contohnya:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Atau:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

Atau:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1

---

Sama seperti masalah sebelumnya dalam siri ini, kita boleh melihat pendekatan pengaturcaraan dinamik dari bawah ke atas di sini juga.

Untuk setiap nilai dalam tatasusunan nums, panjang urutan terbesar yang boleh kita miliki bermula dari indeks $i$i ialah sama ada:

• 1 (nilai itu sendiri)

atau

• 1 bilangan urutan terbesar yang boleh kita miliki bermula dari indeks $i1$i 1 .

Walau bagaimanapun, kami tidak boleh memasukkan pilihan kedua jika nums[i 1] kurang daripada nums[i].

Mula-mula, kita boleh bermula dengan mencipta tatasusunan dp untuk menyimpan panjang urutan yang boleh kita miliki dari setiap indeks nombor dan seterusnya. Iaitu, dp[0] akan mempunyai panjang jujukan terbesar yang boleh kita miliki dari nombor[0] dan seterusnya, dp[1] mempunyai panjang jujukan terbesar yang boleh kita miliki dari nombor[1] dan seterusnya. pada:

let dp = Array.from({ length: nums.length }, () => 1);

Kemudian, kita boleh mula mengulang dari indeks terakhir nombor ke belakang (kerana ia adalah kedudukan paling mudah di mana hanya ada satu cara untuk membentuk urutan seterusnya, hanya mengambil nilai itu sendiri):

for (let i = nums.length - 1; i >= 0; i--) {
 /* ... */
}

Untuk setiap pilihan, kita boleh mengulangi daripada indeks seterusnya untuk melihat sama ada kita boleh memasukkan urutan terbesar yang boleh dibentuk daripada indeks itu dan seterusnya, jika ya, kita boleh mendapatkan nilai maksimum antara dp[i] dan 1 dp[ j]:

for (let i = nums.length - 1; i >= 0; i--) {
  for (let j = i + 1; j < nums.length; j++) {
    if (nums[i] < nums[j]) {
      dp[i] = Math.max(dp[i], 1 + dp[j]);
    }
  }
}

Akhir sekali, kita boleh mengembalikan nilai terbesar dalam dp:

function lengthOfLIS(nums: number[]): number {
  /* ... */
  return Math.max(...dp); 
}

Dan, penyelesaian akhir kelihatan seperti ini:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Kerumitan masa dan ruang

Kerumitan masa ialah $O(n^2)$O(n2) sambil kami mengulangi setiap item dalam angka untuk setiap item dalam angka.
Kerumitan ruang adalah $O(n)$O(n) apabila kita menyimpan tatasusunan dp dan saiznya akan bertambah apabila panjang nombor bertambah.

---

Ini ialah masalah pengaturcaraan dinamik terakhir dalam siri ini. Seterusnya, kita akan memulakan bab baharu pada selang waktu. Sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Susunan Bertambah Terpanjang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!