Maximize length of Non | Python3 program to implement the above approach ; Function to find the maximum length non decreasing subarray by reversing at most one subarray ; dp [ i ] [ j ] be the longest subsequence of a [ 0. . . i ] with first j parts ; Maximum length sub - sequence of ( 0. . ) ; Maximum length sub - sequence of ( 0. . 1. . ) ; Maximum length sub - sequence of ( 0. . 1. .0 . . ) ; Maximum length sub - sequence of ( 0. . 1. .0 . .1 . . ) ; Find the max length subsequence ; Print the answer ; Driver Code
import sys NEW_LINE def main ( arr , n ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( n ) ] for y in range ( 4 ) ] NEW_LINE if arr [ 0 ] == 0 : NEW_LINE INDENT dp [ 0 ] [ 0 ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 1 ] [ 0 ] = 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if arr [ i ] == 0 : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if arr [ i ] == 1 : NEW_LINE INDENT dp [ 1 ] [ i ] = max ( dp [ 1 ] [ i - 1 ] + 1 , dp [ 0 ] [ i - 1 ] + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 1 ] [ i ] = dp [ 1 ] [ i - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if arr [ i ] == 0 : NEW_LINE INDENT dp [ 2 ] [ i ] = max ( [ dp [ 2 ] [ i - 1 ] + 1 , dp [ 1 ] [ i - 1 ] + 1 , dp [ 0 ] [ i - 1 ] + 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 2 ] [ i ] = dp [ 2 ] [ i - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if arr [ i ] == 1 : NEW_LINE INDENT dp [ 3 ] [ i ] = max ( [ dp [ 3 ] [ i - 1 ] + 1 , dp [ 2 ] [ i - 1 ] + 1 , dp [ 1 ] [ i - 1 ] + 1 , dp [ 0 ] [ i - 1 ] + 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 3 ] [ i ] = dp [ 3 ] [ i - 1 ] NEW_LINE DEDENT DEDENT ans = max ( [ dp [ 2 ] [ n - 1 ] , dp [ 1 ] [ n - 1 ] , dp [ 0 ] [ n - 1 ] , dp [ 3 ] [ n - 1 ] ] ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE arr = [ 0 , 1 , 0 , 1 ] NEW_LINE main ( arr , n ) NEW_LINE DEDENT