Longest Non | Function to find the length of the longest non - increasing subsequence ; Stores the prefix and suffix count of 1 s and 0 s respectively ; Store the number of '1' s up to current index i in pre ; Find the prefix sum ; If the current element is '1' , update the pre [ i ] ; Store the number of '0' s over the range [ i , N - 1 ] ; Find the suffix sum ; If the current element is '0' , update post [ i ] ; Stores the maximum length ; Find the maximum value of pre [ i ] + post [ i ] ; Return the answer ; Driver Code
def findLength ( str , n ) : NEW_LINE INDENT pre = [ 0 ] * n NEW_LINE post = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( i != 0 ) : NEW_LINE INDENT pre [ i ] += pre [ i - 1 ] NEW_LINE DEDENT if ( str [ i ] == '1' ) : NEW_LINE INDENT pre [ i ] += 1 NEW_LINE DEDENT DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( i != ( n - 1 ) ) : NEW_LINE INDENT post [ i ] += post [ i + 1 ] NEW_LINE DEDENT if ( str [ i ] == '0' ) : NEW_LINE INDENT post [ i ] += 1 NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans = max ( ans , pre [ i ] + post [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT S = "0101110110100001011" NEW_LINE n = len ( S ) NEW_LINE print ( findLength ( S , n ) ) NEW_LINE