最長非遞增子序列在一個二進位字串中

在這個問題中，我們需要找到給定字串的最長非遞增子序列。

非遞增的意思是字元要麼相同，要麼按降序排列。由於二進位字串僅包含“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 <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中文網其他相關文章！