# Longest Non-Increasing Subsequence in a Binary String

Longest Non-Increasing Subsequence in a Binary StringGiven a binary string S of size N, the task is to find the length of the longest non-increasing subsequence in the given string S.Examples:Input: S = “0101110110100001011”Output: 12 Explanation: The longest non-increasing subsequence is “111111100000”, having length equal to 12.Input: S = 10101Output: 3Approach: The given problem can be solved based on the observation that the string S is a binary string so a non-increasing subsequence will always consist of 0 with more consecutive 1s or 1 with more consecutive 0s. Follow the below steps to solve the problem:Initialize an array, say pre[], that stores the number of 1s till each index i for i over the range [0, N – 1].Initialize an array, say post[], that stores the number of 0s till each index i to the end of the string for i over the range [0, N – 1].Initialize a variable, say ans that stores the length of the longest non-increasing subsequence in the given string S.Iterate over the range [0, N – 1] and update the value of ans to the maximum of ans and (pre[i] + post[i]).After completing the above steps, print the value of ans as the result.Below is the implementation of the above approach:C++  #include using namespace std;  int findLength(string str, int n){            int pre[n], post[n];          memset(pre, 0, sizeof(pre));    memset(post, 0, sizeof(post));              for (int i = 0; i < n; i++) {                  if (i != 0) {            pre[i] += pre[i - 1];        }                          if (str[i] == '1') {            pre[i] += 1;        }    }              for (int i = n - 1; i >= 0; i–) {                  if (i != n – 1)            post[i] += post[i + 1];                          if (str[i] == ‘0’)            post[i] += 1;    }          int ans = 0;              for (int i = 0; i < n; i++) {        ans = max(ans, pre[i] + post[i]);    }          return ans;}  int main(){    string S = "0101110110100001011";    cout