C++ 二进制字符串中最长的非递增子序列

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

非递增的意思是字符要么相同，要么按照递减顺序排列。由于二进制字符串只包含’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的数量。如果I > 0，则将前一个元素的值添加到当前元素的值上。

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

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

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

• 步骤6 −如果当前元素是“0”，则将1添加到当前元素。

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

• 步骤8 −使用循环遍历“pre1s”和“suffix0s”。

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

• 步骤10 −返回“res”变量的值。

示例

对于输入“010100”，前缀数组将为[0, 1, 1, 2, 2, 2]，后缀0的数组将为[4, 3, 3, 2, 2, 1]。和数组将为[4, 4, 4, 4, 4, 1]，和数组中的最大值是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

在这个方法中，我们首先计算总的0的数量。然后，我们开始遍历字符串，并在遇到0时计数1并减少0。还要在每次迭代中将零和一的计数求和，并找到最大的结果值。

步骤

• 步骤1 – 定义’count1’，’count0’和’res’变量，并将它们初始化为0，分别用于存储1的计数、0的计数和最终结果。

• 步骤2 – 通过遍历字符串计算总的0的数量，并将其存储在’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的总数。