非递增的意思是字符要么相同，要么按降序排列。由于二进制字符串仅包含“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 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 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 输出
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 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 输出
The length of the longest non-increasing subsequence in the given binary string is - 6
登录后复制
时间复杂度 - O(N)，因为我们计算字符串中零的总数并遍历字符串以找到最长的子序列。
空间复杂度 - O(1)
结论
这里，两种方法具有相同的时间复杂度但不同的空间复杂度。第二种方法在我们优化代码时使用常量空间，但第一种方法使用动态空间来存储前缀 1 和后缀 0 的总数。
以上就是最长非递增子序列在一个二进制字符串中的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583039.html
