在这个问题中，我们需要找到给定字符串的最长非递增子序列。
非递增的意思是字符要么相同，要么按降序排列。由于二进制字符串仅包含“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。
#includeusing 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”变量的值。
示例
#includeusing 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 的总数。
