最长非递增子序列在一个二进制字符串中

在这个问题中，我们需要找到给定字符串的最长非递增子序列。

非递增的意思是字符要么相同，要么按降序排列。由于二进制字符串仅包含“0”和“1”，因此生成的字符串应以“1”开头并以“0”结尾，或者以“0”或“1”开头和结尾。

为了解决这个问题，我们将统计字符串每个位置的前缀“1”和后缀“0”，并找到前缀“1”和后缀“0”的最大和。

问题陈述 - 我们给出了二进制字符串 str。我们需要从给定的字符串中找到最长的非递增子序列。

示例

Input –  str = "010100"

Output – 4

说明

最长的非递增子序列是“1100”。

Input –  str = "010110010"

Output – 6

说明

最长的非递增子序列是“111000”。

Input –  str = ‘00000000’

Output – 8

说明

最长的非递增子序列是‘00000000’，它等于给定的字符串。

方法 1

在这种方法中，我们将在数组中为每个索引存储前缀“1”和后缀“0”的计数。之后，我们从两个数组中的相同索引获取值，将它们相加，并找到最大总和。

算法

• 步骤 1 - 定义 pre1s 和 suffix0s 数组来存储前缀 1 和后缀 0。另外，将所有数组元素初始化为 0。

• 步骤 2 - 使用 for 循环遍历字符串并计算每个索引的前缀 1。如果我> 0，则将前一个元素的值添加到当前元素。

• 步骤 3 - 如果当前字符为“1”，则将 pre1s[i] 的当前值加 1。

• 第 4 步 - 现在，计算给定字符串中的后缀 0。从末尾开始遍历字符串。

• 步骤 5 - 如果“I”的值不等于“n – 1”，则获取“I + 1”元素的值并将其添加到当前元素。

• 第 6 步 - 如果当前元素为“0”，则向当前元素加 1。

• 第 7 步 - 现在，用 0 初始化“res”变量。

• 第 8 步 - 使用循环迭代“pre1s”和“suffix0s”。

• 第 9 步 - 从“pre1s”和“suffix0s”数组中的第 i 个索引获取值，并将它们相加。另外，如果“sum”大于“res”变量的当前值，则用“sum”值更改“res”变量值。

• 第 10 步 - 返回“res”变量的值。

示例

对于输入‘010100’，前缀数组为 [0, 1, 1, 2, 2, 2]，后缀 0 数组为 [4, 3, 3, 2, 2, 1]。 sum 数组将为 [4, 4, 4, 4, 4, 1]，sum 数组中的最大值为 4。因此，答案将为 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;
}

输出

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

时间复杂度 - O(N)，因为我们需要初始化前缀 1 和后缀 0 的数组。

空间复杂度 - O(N)，因为我们将前缀 1 和后缀 0 存储在数组中

方法2

在这种方法中，我们将首先计算零的总数。之后，我们开始遍历字符串，继续计算“1”，如果找到 0，则减少“0”。此外，我们在每次迭代中将 0 和 1 的计数相加，并找到最大结果值。

算法

• 第 1 步 - 定义 'count1'、'count0' 和 'res' 变量，并用 0 初始化它们，分别存储 1、0 的计数和最终结果.

• 第 2 步 - 通过遍历字符串并将其存储在“count0”变量中来计算零的总数。

• 第 3 步 - 现在，使用循环迭代字符串。

• 步骤 4 - 在循环中，如果当前字符为“1”，则将“count1”的值增加 1，否则将“count0”的值减少1.

• 第 5 步 - 另外，将“res”和“count0 + count1”中的最大值存储到“res”变量中。

• 第 6 步 - 当循环终止时，返回“res”变量的值。

示例

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

输出

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

时间复杂度 - O(N)，因为我们计算字符串中零的总数并遍历字符串以找到最长的子序列。

空间复杂度 - O(1)

结论

这里，两种方法具有相同的时间复杂度但不同的空间复杂度。第二种方法在我们优化代码时使用常量空间，但第一种方法使用动态空间来存储前缀 1 和后缀 0 的总数。

以上是最长非递增子序列在一个二进制字符串中的详细内容。更多信息请关注PHP中文网其他相关文章！