So verwenden Sie den am längsten ansteigenden Teilsequenzalgorithmus in C++

Für die Verwendung des Longest Increasing Subsequence-Algorithmus in C++ sind bestimmte Codebeispiele erforderlich.

Die Longest Increasing Subsequence (LIS) ist ein klassisches Algorithmusproblem, und seine Lösungsideen können auf mehrere Bereiche wie Datenverarbeitung und Graphentheorie angewendet werden , usw. In diesem Artikel werde ich die Verwendung des am längsten ansteigenden Teilsequenzalgorithmus in C++ vorstellen und spezifische Codebeispiele bereitstellen.

Lassen Sie uns zunächst die Definition der am längsten zunehmenden Teilfolge verstehen. Gegeben eine Folge a1, a2, …, an, müssen wir eine längste Teilfolge b1, b2, …, bm finden, in der die relative Reihenfolge der Elemente von b in der ursprünglichen Folge zunimmt. Das heißt, wenn aj > erfüllt ist, existiert auch bj > Die Länge der am längsten ansteigenden Teilfolge beträgt m.

Als nächstes stellen wir zwei gängige Algorithmen zum Lösen der am längsten wachsenden Teilfolge vor: den dynamischen Programmieralgorithmus und den gierigen Algorithmus.

1. Dynamischer Programmieralgorithmus

Der dynamische Programmieralgorithmus unterteilt den Lösungsprozess der am längsten wachsenden Teilfolge in mehrere Stufen und speichert die Ergebnisse in einem zweidimensionalen Array dp. dp[i] stellt die Länge der am längsten ansteigenden Teilsequenz dar, die mit dem i-ten Element in der Sequenz endet.

Der spezifische Lösungsprozess ist wie folgt:

• Alle Elemente des dp-Arrays werden auf 1 initialisiert, was bedeutet, dass die Länge der Teilsequenz, die mit jedem Element endet, mindestens 1 beträgt.
• Durchlaufen Sie die gesamte Sequenz von links nach rechts und berechnen Sie für jede Position i den Wert von dp[i].
• Für jede Position i die vorherige Position j durchlaufen. Wenn aj

Das Endergebnis ist der Maximalwert im dp-Array.

Das Folgende ist ein Codebeispiel für die Implementierung des dynamischen Programmieralgorithmus in C++:

#include<iostream>
#include<vector>
using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
  int n = nums.size();
  vector<int> dp(n, 1);

  for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = max(dp[i], dp[j]+1);
      }
    }
  }

  int res = 0;
  for (int i = 0; i < n; i++) {
    res = max(res, dp[i]);
  }

  return res;
}

int main() {
  vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
  int res = longestIncreasingSubsequence(nums);
  cout << "最长递增子序列的长度为：" << res << endl;
  return 0;
}

2. Greedy-Algorithmus

Der Greedy-Algorithmus ist eine effizientere Möglichkeit, das Problem der längsten zunehmenden Teilsequenz zu lösen. Dieser Algorithmus verwendet ein Hilfsarray d, um das letzte Element der aktuell am längsten ansteigenden Teilsequenz zu speichern. Durchlaufen Sie die gesamte Sequenz und verwenden Sie für jedes Element eine binäre Suche, um seine Position im Hilfsarray d zu bestimmen.

Der spezifische Lösungsprozess ist wie folgt:

• Initialisieren Sie das Hilfsarray d als leeres Array.
• Durchlaufen Sie die gesamte Sequenz von links nach rechts. Wenn a größer als das Endelement von d ist, fügen Sie für jedes Element a a am Ende von d hinzu.
• Wenn a kleiner oder gleich dem letzten Element von d ist, verwenden Sie die binäre Suche, um das erste Element in d zu finden, das größer oder gleich a ist, und ersetzen Sie es durch a.

Das Endergebnis ist die Länge des Hilfsarrays d.

Das Folgende ist ein Codebeispiel für die Implementierung des Greedy-Algorithmus in C++:

#include<iostream>
#include<vector>
using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
  vector<int> d;

  for (auto num : nums) {
    int left = 0, right = d.size() - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (d[mid] < num) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    if (left >= d.size()) {
      d.push_back(num);
    } else {
      d[left] = num;
    }
  }

  return d.size();
}

int main() {
  vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
  int res = longestIncreasingSubsequence(nums);
  cout << "最长递增子序列的长度为：" << res << endl;
  return 0;
}

Das Obige ist eine Einführung und ein Codebeispiel für die Verwendung des am längsten ansteigenden Teilsequenzalgorithmus in C++. Unabhängig davon, ob es sich um einen dynamischen Programmieralgorithmus oder einen gierigen Algorithmus handelt, kann er das Problem der längsten zunehmenden Teilsequenz mit einer Zeitkomplexität von O (n ^ 2) oder O (nlogn) lösen. Leser können basierend auf bestimmten Anwendungsszenarien den geeigneten Algorithmus auswählen. Ich hoffe, dieser Artikel kann jedem helfen, den am längsten zunehmenden Teilsequenzalgorithmus zu verstehen.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den am längsten ansteigenden Teilsequenzalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!