Urutan tidak bertambah terpanjang dalam rentetan binari

Dalam masalah ini, kita perlu mencari urutan tidak bertambah terpanjang bagi rentetan yang diberikan.

Tidak bertambah bermakna watak sama ada sama atau dalam susunan menurun. Memandangkan rentetan binari hanya mengandungi "0" dan "1", rentetan yang terhasil hendaklah sama ada bermula dengan "1" dan berakhir dengan "0", atau bermula dan berakhir dengan "0" atau "1".

Untuk menyelesaikan masalah ini, kami akan mengira awalan "1" dan akhiran "0" pada setiap kedudukan rentetan dan mencari jumlah maksimum awalan "1" dan akhiran "0".

Pernyataan Masalah - Kami diberi rentetan binari str. Kita perlu mencari urutan tidak bertambah terpanjang daripada rentetan yang diberikan.

Contoh

Input –  str = "010100"

Output – 4

Arahan

Jujukan tidak bertambah yang paling lama ialah "1100".

Input –  str = "010110010"

Output – 6

Arahan

Jujukan tidak bertambah terpanjang ialah "111000".

Input –  str = ‘00000000’

Output – 8

Arahan

Jujukan tidak bertambah terpanjang ialah '00000000', yang sama dengan rentetan yang diberikan.

Kaedah 1

Dalam kaedah ini kita akan menyimpan kiraan awalan '1' dan akhiran '0' untuk setiap indeks dalam tatasusunan. Selepas itu, kami mendapat nilai daripada indeks yang sama dalam kedua-dua tatasusunan, tambahkannya, dan cari jumlah maksimum.

Algoritma

• Langkah 1 - Tentukan tatasusunan pra1 dan akhiran0 untuk menyimpan awalan 1 dan akhiran 0. Selain itu, mulakan semua elemen tatasusunan kepada 0.

• Langkah 2 - Gunakan gelung for untuk lelaran melalui rentetan dan hitung awalan 1 untuk setiap indeks. Jika i > 0, maka nilai elemen sebelumnya ditambah pada elemen semasa.

• Langkah 3 - Jika aksara semasa ialah "1", tambah 1 pada nilai semasa pra1s[i].

• Langkah 4 - Sekarang, hitung akhiran 0 dalam rentetan yang diberikan. Lintas rentetan bermula dari hujung.

• Langkah 5 - Jika nilai "I" tidak sama dengan "n – 1", maka dapatkan nilai elemen "I + 1" dan tambahkannya pada elemen semasa.

• Langkah 6 - Jika elemen semasa ialah "0", tambah 1 pada elemen semasa.

• Langkah 7 - Sekarang, mulakan pembolehubah "res" dengan 0.

• Langkah 8 - Ulangi "pre1s" dan "suffix0s" menggunakan gelung.

• Langkah 9 - Dapatkan nilai daripada indeks ke-i dalam tatasusunan "pre1s" dan "suffix0s" dan tambahkannya bersama-sama. Selain itu, jika "jumlah" lebih besar daripada nilai semasa pembolehubah "res", nilai pembolehubah "res" ditukar dengan nilai "jumlah".

• Langkah 10 - Kembalikan nilai pembolehubah "res".

Contoh

Untuk input '010100', tatasusunan awalan ialah [0, 1, 1, 2, 2, 2] dan tatasusunan akhiran 0 ialah [4, 3, 3, 2, 2, 1]. Tatasusunan jumlah ialah [4, 4, 4, 4, 4, 1] dan nilai maksimum dalam tatasusunan jumlah ialah 4. Oleh itu, jawapannya ialah 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;
}

Output

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

Kerumitan masa - O(N) kerana kita perlu memulakan tatasusunan dengan awalan 1 dan akhiran 0.

Kerumitan ruang - O(N) kerana kami menyimpan awalan 1 dan akhiran 0 dalam tatasusunan

Kaedah 2

Dalam kaedah ini kita akan mengira jumlah sifar terlebih dahulu. Selepas itu, kami mula mengulang melalui rentetan, terus mengira "1" s, dan jika 0 ditemui, mengurangkannya dengan "0" s. Selain itu, kami menambah kiraan 0 dan 1 dalam setiap lelaran dan mencari nilai terhasil maksimum.

Algoritma

• Langkah 1 - Tentukan pembolehubah 'count1', 'count0' dan 'res' dan mulakannya dengan 0 untuk menyimpan kiraan 1, 0 dan hasil akhir masing-masing.

• Langkah 2 - Kira jumlah bilangan sifar dengan menggelung melalui rentetan dan menyimpannya dalam pembolehubah "count0".

• Langkah 3 - Sekarang, ulangi rentetan menggunakan gelung.

• Langkah 4 - Dalam gelung, jika aksara semasa ialah "1", tingkatkan nilai "count1" sebanyak 1, jika tidak kurangkan nilai "count0" sebanyak 1.

• Langkah 5 - Selain itu, simpan nilai maksimum daripada "res" dan "count0 + count1" ke dalam pembolehubah "res".

• Langkah 6 - Apabila gelung ditamatkan, kembalikan nilai pembolehubah "res".

Contoh

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

Output

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

Kerumitan Masa - O(N) semasa kita mengira jumlah sifar dalam rentetan dan melintasi rentetan untuk mencari urutan terpanjang.

Kerumitan ruang - O(1)

Kesimpulan

Di sini, kedua-dua kaedah mempunyai kerumitan masa yang sama tetapi kerumitan ruang yang berbeza. Kaedah kedua menggunakan ruang malar apabila kami mengoptimumkan kod, tetapi kaedah pertama menggunakan ruang dinamik untuk menyimpan jumlah bilangan awalan 1 dan akhiran 0.

Atas ialah kandungan terperinci Urutan tidak bertambah terpanjang dalam rentetan binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!