在這個問題中，我們需要找到給定字串的最長非遞增子序列。
非遞增的意思是字元要麼相同，要麼按降序排列。由於二進位字串僅包含“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中文網其他相關文章！
