LeetCode-Meditationen: Längste ansteigende Folge

In der Beschreibung dieses Problems heißt es einfach:

Gibt bei einem gegebenen ganzzahligen Array nums die Länge der längsten streng ansteigenden Teilsequenz zurück.

Zum Beispiel:

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.

Oder:

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

Oder:

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

---

Ähnlich wie beim vorherigen Problem in dieser Serie können wir auch hier einen dynamischen Bottom-up-Programmieransatz betrachten.

Für jeden Wert im Nums-Array die Länge der größten Teilsequenz, die wir ausgehend vom Index haben können $\mathrm{ich}$ich ist entweder:

• 1 (dieser Wert selbst)

oder

• 1 die Nummer der größten Teilfolge, die wir ausgehend vom Index haben können $i1$ich 1 .

Allerdings können wir die zweite Option nicht einschließen, wenn nums[i 1] kleiner als nums[i] ist.

Zuerst können wir damit beginnen, ein dp-Array zu erstellen, um die Länge der Teilsequenzen zu speichern, die wir ab jedem Nums-Index haben können. Das heißt, dp[0] hat die Länge der größten Teilsequenz, die wir ab nums[0] haben können, dp[1] hat die Länge der größten Teilsequenz, die wir ab nums[1] haben können, und so weiter am:

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

Dann können wir mit der Iteration ab dem letzten Zahlenindex rückwärts beginnen (da dies die einfachste Position ist, bei der es nur eine Möglichkeit gibt, eine Teilfolge weiter zu bilden, indem wir einfach den Wert selbst nehmen):

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

Für jede Option können wir vom nächsten Index aus iterieren, um zu sehen, ob wir die größte Teilsequenz einbeziehen können, die ab diesem Index gebildet werden kann. Wenn ja, können wir den Maximalwert zwischen dp[i] und 1 dp[ erhalten 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]);
    }
  }
}

Endlich können wir den größten Wert in dp zurückgeben:

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

Und die endgültige Lösung sieht so aus:

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.

Zeit- und Raumkomplexität

Die zeitliche Komplexität ist $O(n^2)$O(n2) während wir jedes Element in Zahlen durchlaufen für jedes Element in Zahlen.
Die Raumkomplexität ist $O(n)$O(n) Da wir ein dp-Array behalten und seine Größe mit zunehmender Länge der Nummern zunimmt.

---

Dies war das letzte Problem der dynamischen Programmierung in dieser Serie. Als nächstes beginnen wir ein neues Kapitel über Intervalle. Bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Längste ansteigende Folge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!