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.

Beispiel

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

Erklärung

Erklärung

• Der erste Schritt besteht darin, zwei Arrays,lisundlds, mit der gleichen Länge wie das Eingabearrayarrzu initialisieren und mit Einsen zu füllen.lissteht für „längste zunehmende Teilfolge“,ldssteht 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 mitarr[i]endet. Dies wird durch verschachtelte Schleifen erreicht, bei denenjvon 0 bisi-1reicht. Wennarr[i] > arr[j], aktualisieren wirlis[i]auf seinen aktuellen Wert und das Maximum vonlis[j] + 1.

• Der nächste Schritt besteht darin,lds[i]zu berechnen, was die Länge der längsten abnehmenden Teilfolge abarr[i]ist. Dies erfolgt über verschachtelte Schleifen, wobeijvonn-1bisi+1reicht. Wennarr[i] > arr[j], aktualisieren wirlds[i]auf das Maximum seines aktuellen Werts undlds[j] + 1.

• Schließlich durchlaufen wir dienElemente des Eingabearrays und finden den Maximalwert vonlis[i] + lds[i] - 1, der den Maximalwert darstellt, der mitarr[i] endet und beginnt.Die Länge der langen Bitsequenz. Dieser Wert wird in der VariablenmaxLengthgespeichert.

• Diese Funktion gibtmaxLengthzurü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!