Längste nicht ansteigende Teilsequenz in einer Binärzeichenfolge

In diesem Problem müssen wir die längste nicht zunehmende Teilfolge einer bestimmten Zeichenfolge finden.

Nicht aufsteigend bedeutet, dass die Zeichen entweder gleich oder in absteigender Reihenfolge sind. Da Binärzeichenfolgen nur „0“ und „1“ enthalten, sollte die resultierende Zeichenfolge entweder mit „1“ beginnen und mit „0“ enden oder mit „0“ oder „1“ beginnen und enden.

Um dieses Problem zu lösen, zählen wir das Präfix „1“ und das Suffix „0“ an jeder Position der Zeichenfolge und ermitteln die maximale Summe aus dem Präfix „1“ und dem Suffix „0“.

Problemstellung - Wir erhalten eine binäre Zeichenfolge str. Wir müssen die längste nicht zunehmende Teilsequenz aus der gegebenen Zeichenfolge finden.

Beispiel

Input –  str = "010100"

Output – 4

Anleitung

Die längste nicht ansteigende Teilsequenz ist „1100“.

Input –  str = "010110010"

Output – 6

Anleitung

Die längste nicht ansteigende Teilsequenz ist „111000“.

Input –  str = ‘00000000’

Output – 8

Anleitung

Die längste nicht ansteigende Teilsequenz ist „00000000“, was der angegebenen Zeichenfolge entspricht.

Methode 1

In dieser Methode speichern wir die Anzahl des Präfixes „1“ und des Suffixes „0“ für jeden Index im Array. Danach erhalten wir die Werte aus demselben Index in beiden Arrays, addieren sie und ermitteln die maximale Summe.

Algorithmus

• Schritt 1 – Definieren Sie pre1s- und suffix0s-Arrays, um Präfix 1 und Suffix 0 zu speichern. Initialisieren Sie außerdem alle Array-Elemente auf 0.

• Schritt 2 – Verwenden Sie eine for-Schleife, um die Zeichenfolge zu durchlaufen und das Präfix 1 für jeden Index zu berechnen. Wenn i > 0, wird der Wert des vorherigen Elements zum aktuellen Element addiert.

• Schritt 3 – Wenn das aktuelle Zeichen „1“ ist, addieren Sie 1 zum aktuellen Wert von pre1s[i].

• Schritt 4 – Zählen Sie nun das Suffix 0 in der angegebenen Zeichenfolge. Durchlaufen Sie die Zeichenfolge vom Ende beginnend.

• Schritt 5 – Wenn der Wert von „I“ nicht gleich „n – 1“ ist, dann ermitteln Sie den Wert des Elements „I + 1“ und addieren Sie ihn zum aktuellen Element.

• Schritt 6 – Wenn das aktuelle Element „0“ ist, addieren Sie 1 zum aktuellen Element.

• Schritt 7 – Initialisieren Sie nun die Variable „res“ mit 0.

• Schritt 8 – Mit einer Schleife über „pre1s“ und „suffix0s“ iterieren.

• Schritt 9 – Holen Sie sich den Wert aus dem i-ten Index in den Arrays „pre1s“ und „suffix0s“ und addieren Sie sie. Wenn „sum“ außerdem größer als der aktuelle Wert der Variablen „res“ ist, wird der Wert der Variable „res“ durch den Wert „sum“ geändert.

• Schritt 10 – Geben Sie den Wert der Variablen „res“ zurück.

Beispiel

Für die Eingabe „010100“ ist das Präfix-Array [0, 1, 1, 2, 2, 2] und das Suffix-0-Array [4, 3, 3, 2, 2, 1]. Das Summenarray ist [4, 4, 4, 4, 4, 1] und der Maximalwert im Summenarray ist 4. Daher lautet die Antwort 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;
}

Ausgabe

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

Zeitkomplexität – O(N), da wir das Array mit Präfix 1 und Suffix 0 initialisieren müssen.

Raumkomplexität – O(N), da wir Präfix 1 und Suffix 0 im Array speichern

Methode 2

Bei dieser Methode zählen wir zunächst die Gesamtzahl der Nullen. Danach beginnen wir mit der Iteration durch die Zeichenfolge, zählen weiterhin „1“-Werte und dekrementieren den Wert um „0“, wenn eine 0 gefunden wird. Zusätzlich addieren wir in jeder Iteration die Anzahl von 0 und 1 und ermitteln den maximalen resultierenden Wert.

Algorithmus

• Schritt 1 – Definieren Sie die Variablen „count1“, „count0“ und „res“ und initialisieren Sie sie mit 0, um die Anzahl und das Endergebnis von 1 bzw. 0 zu speichern.

• Schritt 2 – Zählen Sie die Gesamtzahl der Nullen, indem Sie die Zeichenfolge durchlaufen und sie in der Variablen „count0“ speichern.

• Schritt 3 – Nun iterieren Sie mit einer Schleife über die Zeichenfolge.

• Schritt 4 – Wenn in der Schleife das aktuelle Zeichen „1“ ist, erhöhen Sie den Wert von „count1“ um 1, andernfalls verringern Sie den Wert von „count0“ um 1.

• Schritt 5 – Speichern Sie außerdem den Maximalwert aus „res“ und „count0 + count1“ in der Variablen „res“.

• Schritt 6 – Wenn die Schleife endet, geben Sie den Wert der Variablen „res“ zurück.

Beispiel

#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;
}

Ausgabe

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

Zeitkomplexität – O(N), da wir die Gesamtzahl der Nullen in der Zeichenfolge zählen und die Zeichenfolge durchlaufen, um die längste Teilsequenz zu finden.

Raumkomplexität – O(1)

Fazit

Hier haben beide Methoden die gleiche Zeitkomplexität, aber unterschiedliche räumliche Komplexität. Die zweite Methode verwendet konstanten Speicherplatz, wenn wir den Code optimieren, aber die erste Methode verwendet dynamischen Speicherplatz, um die Gesamtzahl von Präfix 1 und Suffix 0 zu speichern.

Das obige ist der detaillierte Inhalt vonLängste nicht ansteigende Teilsequenz in einer Binärzeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!