JavaScript-Programm zum Finden der längsten bimodalen Teilsequenz |

Wir werden dynamische Programmierung verwenden, um die längste bitonale Sequenz in jedem Array zu finden. Eine bitonale Sequenz ist eine Sequenz, die zunächst zunimmt und dann abnimmt. Um die längste bitonale Sequenz zu finden, verwenden wir einen zweistufigen Ansatz. Suchen Sie zunächst die am längsten ansteigende Teilsequenz im angegebenen Array und dann die am längsten absteigende Teilsequenz in umgekehrter Reihenfolge des angegebenen Arrays. Schließlich addieren wir die Längen der beiden Teilsequenzen und subtrahieren 1, um die gemeinsamen Elemente in der Mitte auszuschließen.

Methode

Eine bitonische Sequenz ist eine Sequenz, die zuerst zunimmt und dann abnimmt. Der Weg, die längste bitonale Sequenz in einem bestimmten Array zu finden, ist die Verwendung dynamischer Programmierung.

• Initialisieren Sie zwei Arrays „inc“ und „dec“, um die Länge der am längsten ansteigenden Teilsequenz zu speichern, die an jedem Index endet.

• Durchlaufen Sie das Array und aktualisieren Sie die Werte von „inc“ und „dec“ an jedem Index unter Verwendung des Werts am vorherigen Index.

• Finden Sie den Maximalwert der Summe von „inc“ und „dec“ minus eins an jedem Index, da dies die Länge der längsten Bit-erhöhenden Teilsequenz ergibt, die diesen Index enthält.

• Gibt den in Schritt 3 gefundenen Maximalwert als Länge der längsten Bit-erhöhenden Teilsequenz zurück.

• Um die längste bitonale Sequenz zu rekonstruieren, verwenden Sie die Werte in „inc“ und „dec“, um ausgehend vom Index, der in Schritt 3 den Maximalwert ergab, zurückzugehen.

• Gibt die rekonstruierte Sequenz als längste bitonale Sequenz zurück.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Hier ist ein vollständiges Arbeitsbeispiel eines JavaScript-Programms zum Finden der längsten bitonischen Teilsequenz mithilfe dynamischer Programmierung −

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)); 

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

• Der erste Schritt besteht darin, zwei Arrays, lis und lds, mit der gleichen Länge wie das Eingabearray arr zu initialisieren und mit Einsen zu füllen. lis steht für „längste zunehmende Teilfolge“, lds steht für „längste abnehmende Teilfolge“.

• Der nächste Schritt besteht darin, lis[i] zu berechnen, was die Länge der am längsten ansteigenden Teilsequenz ist, die mit arr[i] endet. Dies wird durch verschachtelte Schleifen erreicht, bei denen j von 0 bis i-1 reicht. Wenn arr[i] > arr[j], aktualisieren wir lis[i] auf seinen aktuellen Wert und das Maximum von lis[j] + 1.

• Der nächste Schritt besteht darin, lds[i] zu berechnen, was die Länge der längsten abnehmenden Teilfolge ab arr[i] ist. Dies erfolgt über verschachtelte Schleifen, wobei j von n-1 bis i+1 reicht. Wenn arr[i] > arr[j], aktualisieren wir lds[i] auf das Maximum seines aktuellen Werts und lds[j] + 1.

• Schließlich durchlaufen wir die n Elemente des Eingabearrays und finden den Maximalwert von lis[i] + lds[i] - 1, der den Maximalwert darstellt, der mit arr[i] endet und beginnt. Die Länge der langen Bitsequenz. Dieser Wert wird in der Variablen maxLength gespeichert.

• Diese Funktion gibt maxLength zurück, was die Länge der längsten Bit-erhöhenden Teilsequenz im Eingabearray ist.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Finden der längsten bimodalen Teilsequenz |. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!