Programme JavaScript pour trouver la sous-séquence bimodale la plus longue |

Nous utiliserons la programmation dynamique pour trouver la séquence bitonale la plus longue dans chaque tableau. Une séquence bitonale est une séquence qui augmente d’abord puis diminue. Pour trouver la séquence bitonale la plus longue, nous utiliserons une approche en deux étapes. Tout d’abord, recherchez la sous-séquence croissante la plus longue dans le tableau donné, puis recherchez la sous-séquence décroissante la plus longue dans l’ordre inverse du tableau donné. Enfin, nous additionnons les longueurs des deux sous-séquences et soustrayons 1 pour exclure les éléments communs au milieu.

Méthode

Une séquence bitonique est une séquence qui augmente d’abord puis diminue. La façon de trouver la séquence bitonale la plus longue dans un tableau donné consiste à utiliser la programmation dynamique.

• Initialisez deux tableaux "inc" et "dec" pour stocker la longueur de la sous-séquence croissante la plus longue se terminant à chaque index.

• Parcourez le tableau en mettant à jour les valeurs de "inc" et "dec" à chaque index en utilisant la valeur de l'index précédent.

• Trouvez la valeur maximale de la somme de "inc" et "dec" moins un à chaque index, car cela donnera la longueur de la plus longue sous-séquence croissante en bits contenant cet index.

• Renvoyer la valeur maximale trouvée à l'étape 3 comme longueur de la sous-séquence croissante en bits la plus longue.

• Pour reconstruire la séquence bitonale la plus longue, utilisez les valeurs en "inc" et "dec" pour revenir en arrière à partir de l'index qui a donné la valeur maximale à l'étape 3.

• Renvoyer la séquence reconstruite comme la séquence bitonale la plus longue.

Exemple

Exemple

Voici un exemple fonctionnel complet d'un programme JavaScript pour trouver la sous-séquence bitonique la plus longue en utilisant la programmation dynamique −

function LBSLength(arr) {
   let n = arr.length;
   let lis = new Array(n).fill(1);
   let lds = new Array(n).fill(1);
     
   for (let i = 1; i < n; i++) {
      for (let j = 0; j < i; j++) {
         if (arr[i] > arr[j]) {
            lis[i] = Math.max(lis[i], lis[j] + 1);
         }
      }
   }
     
   for (let i = n - 2; i >= 0; i--) {
      for (let j = n - 1; j > i; j--) {
         if (arr[i] > arr[j]) {
            lds[i] = Math.max(lds[i], lds[j] + 1);
         }
      }
   }
     
   let maxLength = 0;
   for (let i = 0; i < n; i++) {
      maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);
   }
    
   return maxLength;
}

const arr = [1, 7, 8, 11, 5, 2, 3];
console.log(LBSLength(arr)); 

Explication

Explication

• La première étape consiste à initialiser deux tableaux, lis et lds, de même longueur que le tableau d'entrée arr et remplis de uns. lis signifie « sous-séquence croissante la plus longue », lds signifie « sous-séquence décroissante la plus longue ».

• L'étape suivante consiste à calculer lis[i], qui est la longueur de la sous-séquence croissante la plus longue se terminant par arr[i]. Ceci est réalisé grâce à des boucles imbriquées où j va de 0 à i-1. Si arr[i] > arr[j], nous mettons à jour lis[i] à sa valeur actuelle et au maximum de lis[j] + 1.

• L'étape suivante consiste à calculer lds[i], qui est la longueur de la sous-séquence décroissante la plus longue à partir de arr[i]. Cela se fait via des boucles imbriquées où j va de n-1 à i+1. Si arr[i] > arr[j], on met à jour lds[i] au maximum de sa valeur actuelle et lds[j] + 1.

• Enfin, nous parcourons les éléments n du tableau d'entrée et trouvons la valeur maximale de lis[i] + lds[i] - 1, qui représente la valeur maximale se terminant et commençant par arr[i] La longueur de la longue séquence de bits. Cette valeur est stockée dans la variable maxLength.

• Cette fonction renvoie maxLength, qui est la longueur de la sous-séquence croissante en bits la plus longue du tableau d'entrée.

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!