Sous-séquence non croissante la plus longue dans une chaîne binaire

Dans ce problème, nous devons trouver la sous-séquence non croissante la plus longue d'une chaîne donnée.

Non croissant signifie que les caractères sont soit les mêmes, soit par ordre décroissant. Étant donné que les chaînes binaires ne contiennent que « 0 » et « 1 », la chaîne résultante doit soit commencer par « 1 » et se terminer par « 0 », soit commencer et se terminer par « 0 » ou « 1 ».

Pour résoudre ce problème, nous allons compter le préfixe "1" et le suffixe "0" à chaque position de la chaîne et trouver la somme maximale du préfixe "1" et du suffixe "0".

Énoncé du problème - On nous donne une chaîne binaire str. Nous devons trouver la sous-séquence non croissante la plus longue de la chaîne donnée.

Exemple

Input –  str = "010100"

Output – 4

Instructions

La sous-séquence non croissante la plus longue est "1100".

Input –  str = "010110010"

Output – 6

Instructions

La sous-séquence non croissante la plus longue est "111000".

Input –  str = ‘00000000’

Output – 8

Instructions

La sous-séquence non croissante la plus longue est « 00000000 », qui est égale à la chaîne donnée.

Méthode 1

Dans cette méthode, nous stockerons le nombre de préfixes « 1 » et de suffixes « 0 » pour chaque index du tableau. Après cela, nous obtenons les valeurs du même index dans les deux tableaux, les ajoutons et trouvons la somme maximale.

Algorithme

• Étape 1 - Définissez les tableaux pre1s et suffix0s pour stocker le préfixe 1 et le suffixe 0. De plus, initialisez tous les éléments du tableau à 0.

• Étape 2 - Utilisez une boucle for pour parcourir la chaîne et calculer le préfixe 1 pour chaque index. Si i > 0, alors la valeur de l'élément précédent est ajoutée à l'élément actuel.

• Étape 3 - Si le caractère actuel est "1", ajoutez 1 à la valeur actuelle de pre1s[i].

• Étape 4 - Maintenant, comptez le suffixe 0 dans la chaîne donnée. Parcourez la chaîne en commençant par la fin.

• Étape 5 - Si la valeur de "I" n'est pas égale à "n – 1", alors récupérez la valeur de l'élément "I + 1" et ajoutez-la à l'élément actuel.

• Étape 6 - Si l'élément actuel est "0", ajoutez 1 à l'élément actuel.

• Étape 7 - Maintenant, initialisez la variable « res » avec 0.

• Étape 8 - Parcourez les "pre1s" et les "suffix0s" à l'aide d'une boucle.

• Étape 9 - Obtenez la valeur du i-ème index dans les tableaux "pre1s" et "suffix0s" et additionnez-les ensemble. De plus, si « sum » est supérieur à la valeur actuelle de la variable « res », la valeur de la variable « res » est modifiée avec la valeur « sum ».

• Étape 10 - Renvoyez la valeur de la variable "res".

Exemple

Pour l'entrée « 010100 », le tableau de préfixes est [0, 1, 1, 2, 2, 2] et le tableau de suffixes 0 est [4, 3, 3, 2, 2, 1]. Le tableau de somme sera [4, 4, 4, 4, 4, 1] et la valeur maximale dans le tableau de somme est 4. La réponse sera donc 4.

#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
   // To store the prefix count of '1's and suffix count of '0's
   int pre1s[n] = {0},
      suffix0s[n] = {0};
   for (int i = 0; i < n; i++){
   
      // get the prefix count of '1's
      if (i > 0){
         pre1s[i] += pre1s[i - 1];
      }
      
      // If the current character is '1', then update the pre1s array by adding 1; else, keep it as it is.
      if (str[i] == '1'){
         pre1s[i] += 1;
      }
   }
   
   // get suffix count of '0's
   for (int i = n - 1; i >= 0; i--) {
   
      // add the suffix count of '0's
      if (i != n - 1)
         suffix0s[i] += suffix0s[i + 1];
         
      // If the current character is '0', then update the suffix0s array by adding 1; else, keep it as it is.
      if (str[i] == '0')
         suffix0s[i] += 1;
   }
   
   // to store the final result value
   int res = 0;
   
   // iterate over the pre1s[] and suffix0s[] array and find the maximum value of pre1s[i] + suffix0s[i]
   for (int i = 0; i < n; i++){
      res = max(res, pre1s[i] + suffix0s[i]);
   }
   
   // Return the result
   return res;
}

// Driver Code
int main(){
   string str = "010100";
   int N = str.length();
   cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
   return 0;
}

Sortie

The length of the longest non-increasing subsequence in the given binary string is - 4

Complexité temporelle - O(N) car nous devons initialiser le tableau avec le préfixe 1 et le suffixe 0.

Complexité spatiale - O(N) puisque nous stockons le préfixe 1 et le suffixe 0 dans un tableau

Méthode 2

Dans cette méthode, nous compterons d’abord le nombre total de zéros. Après cela, nous commençons à parcourir la chaîne, en continuant à compter les "1", et si un 0 est trouvé, en le décrémentant de "0". De plus, nous additionnons les comptes de 0 et 1 à chaque itération et trouvons la valeur maximale résultante.

Algorithme

• Étape 1 - Définissez les variables 'count1', 'count0' et 'res' et initialisez-les avec 0 pour stocker le décompte et le résultat final de 1, 0 respectivement.

• Étape 2 - Comptez le nombre total de zéros en parcourant la chaîne et en la stockant dans la variable "count0".

• Étape 3 - Maintenant, parcourez la chaîne à l'aide d'une boucle.

• Étape 4 - Dans la boucle, si le caractère courant est "1", augmentez la valeur de "count1" de 1, sinon diminuez la valeur de "count0" de 1.

• Étape 5 - Stockez également la valeur maximale de "res" et "count0 + count1" dans la variable "res".

• Étape 6 - Lorsque la boucle se termine, renvoyez la valeur de la variable "res".

Exemple

#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
   int count1 = 0, count0 = 0;
   int res = 0;
   // counting total zeros in the string
   for (int i = 0; i < n; i++){
      if (str[i] == '0')
         count0++;
   }
   
   // counting 1s from left, subtracting zeros from total zeros and adding both counts.
   for (int i = 0; i < n; i++){
      if (str[i] == '1')
         count1++;
      else
         count0--;
      res = max(res, count1 + count0);
   }
   return res;
}
int main(){
   string str = "010110010";
   int N = str.length();
   cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
   return 0;
}

Sortie

The length of the longest non-increasing subsequence in the given binary string is - 6

Complexité temporelle - O(N) lorsque nous comptons le nombre total de zéros dans la chaîne et parcourons la chaîne pour trouver la sous-séquence la plus longue.

Complexité spatiale - O(1)

Conclusion

Ici, les deux méthodes ont la même complexité temporelle mais une complexité spatiale différente. La deuxième méthode utilise un espace constant lorsque nous optimisons le code, mais la première méthode utilise un espace dynamique pour stocker le nombre total de préfixe 1 et de suffixe 0.

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!