Méditations LeetCode : sous-séquence croissante la plus longue

La description de ce problème indique simplement :

Étant donné un tableau d'entiers nums, renvoie la longueur de la sous-séquence strictement croissante la plus longue.

Par exemple :

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.

Ou :

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

Ou :

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

---

Semblable au problème précédent de cette série, nous pouvons également examiner ici une approche de programmation dynamique ascendante.

Pour chaque valeur du tableau nums, la longueur de la plus grande sous-séquence que nous pouvons avoir à partir de l'index $i$i est soit :

• 1 (cette valeur elle-même)

ou

• 1 le numéro de la plus grande sous-séquence que l'on peut avoir à partir de l'index $i1$je 1 .

Cependant, nous ne pouvons pas inclure la deuxième option si nums[i 1] est inférieur à nums[i].

Tout d'abord, nous pouvons commencer par créer un tableau dp pour contenir la longueur des sous-séquences que nous pouvons avoir à partir de chaque index de nombres. Autrement dit, dp[0] aura la longueur de la plus grande sous-séquence que nous pouvons avoir à partir de nums[0], dp[1] aura la longueur de la plus grande sous-séquence que nous pouvons avoir à partir de nums[1], et ainsi sur :

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

Ensuite, nous pouvons commencer à itérer à partir du dernier index de nombres vers l'arrière (car c'est la position la plus simple où il n'y a qu'une seule façon de former une sous-séquence, en prenant simplement la valeur elle-même) :

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

Pour chaque option, nous pouvons parcourir à partir de l'index suivant pour voir si nous pouvons inclure la plus grande sous-séquence pouvant être formée à partir de cet index, si c'est le cas, nous pouvons obtenir la valeur maximale entre dp[i] et 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]);
    }
  }
}

Enfin, nous pouvons renvoyer la plus grande valeur en dp :

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

Et la solution finale ressemble à ceci :

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.

Complexité temporelle et spatiale

La complexité temporelle est $O(n^2)$O(n2) au fur et à mesure que nous parcourons chaque élément en chiffres pour chaque élément en chiffres.
La complexité spatiale est $O(n)$O(n) car nous gardons un tableau dp et sa taille augmentera à mesure que la longueur des nombres augmente.

---

C'était le dernier problème de programmation dynamique de cette série. Ensuite, nous commencerons un nouveau chapitre sur les intervalles. En attendant, bon codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!