在这个问题中，我们需要找到给定字符串的最长非递增子序列。
非递增的意思是字符要么相同，要么按降序排列。由于二进制字符串仅包含“0”和“1”，因此生成的字符串应以“1”开头并以“0”结尾，或者以“0”或“1”开头和结尾。
为了解决这个问题，我们将统计字符串每个位置的前缀“1”和后缀“0”，并找到前缀“1”和后缀“0”的最大和。
问题陈述 - 我们给出了二进制字符串 str。我们需要从给定的字符串中找到最长的非递增子序列。
示例
Input – str = "010100"
登录后复制
说明
最长的非递增子序列是“1100”。
Input – str = "010110010"
登录后复制
说明
最长的非递增子序列是“111000”。
Input – str = ‘00000000’
登录后复制
说明
最长的非递增子序列是‘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中文网其他相关文章！
