Comment utiliser l'algorithme de sous-séquence croissante la plus longue en C++

Comment utiliser l'algorithme de sous-séquence croissante la plus longue en C++ nécessite des exemples de code spécifiques

La sous-séquence croissante la plus longue (LIS) est un problème d'algorithme classique, et ses idées de solution peuvent être appliquées à plusieurs domaines tels que le traitement des données, la théorie des graphes. , etc. Dans cet article, je vais présenter comment utiliser l'algorithme de sous-séquence croissante la plus longue en C++ et fournir des exemples de code spécifiques.

Tout d’abord, comprenons la définition de la sous-séquence croissante la plus longue. Étant donné une séquence a1, a2, …, an, nous devons trouver une sous-séquence la plus longue b1, b2, …, bm, dans laquelle l'ordre relatif des éléments de b dans la séquence d'origine augmente. C'est-à-dire que pour tout i ai est satisfait, alors bj > La longueur de la sous-séquence croissante la plus longue est m.

Ensuite, nous présenterons deux algorithmes courants pour résoudre la sous-séquence croissante la plus longue : l'algorithme de programmation dynamique et l'algorithme glouton.

1. Algorithme de programmation dynamique

L'algorithme de programmation dynamique divise le processus de solution de la sous-séquence croissante la plus longue en plusieurs étapes et stocke les résultats dans un tableau bidimensionnel dp. dp[i] représente la longueur de la sous-séquence croissante la plus longue se terminant par le i-ème élément de la séquence.

Le processus de solution spécifique est le suivant :

• Initialisez tous les éléments du tableau dp à 1, ce qui signifie que la longueur de la sous-séquence se terminant par chaque élément est d'au moins 1.
• Parcourez toute la séquence de gauche à droite, et pour chaque position i, calculez la valeur de dp[i].
• Pour chaque position i, parcourez sa position précédente j. Si aj

Le résultat final est la valeur maximale dans le tableau dp.

Ce qui suit est un exemple de code pour implémenter l'algorithme de programmation dynamique en 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. Algorithme glouton

L'algorithme glouton est un moyen plus efficace de résoudre le problème de sous-séquence croissante la plus longue. Cet algorithme utilise un tableau auxiliaire d pour enregistrer le dernier élément de la sous-séquence croissante actuelle la plus longue. Parcourez toute la séquence et pour chaque élément, utilisez la recherche binaire pour déterminer sa position dans le tableau auxiliaire d.

Le processus de solution spécifique est le suivant :

• Initialisez le tableau auxiliaire d en tant que tableau vide.
• Parcourez toute la séquence de gauche à droite, pour chaque élément a, si a est supérieur à l'élément final de d, ajoutez a à la fin de d.
• Si a est inférieur ou égal au dernier élément de d, utilisez la recherche binaire pour trouver le premier élément de d qui est supérieur ou égal à a et remplacez-le par a.

Le résultat final est la longueur du tableau auxiliaire d.

Ce qui suit est un exemple de code d'implémentation de l'algorithme glouton en 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;
}

Ce qui précède est une introduction et un exemple de code sur la façon d'utiliser l'algorithme de sous-séquence croissante la plus longue en C++. Qu'il s'agisse d'un algorithme de programmation dynamique ou d'un algorithme glouton, il peut résoudre le problème de sous-séquence croissante la plus longue avec une complexité temporelle de O(n^2) ou O(nlogn). Les lecteurs peuvent choisir l'algorithme approprié à utiliser en fonction de scénarios d'application spécifiques. J'espère que cet article pourra aider tout le monde à comprendre l'algorithme de sous-séquence croissante la plus longue.

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!