Maximize length of Non | 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
function main_fun ( arr , n ) { var dp = Array . from ( Array ( 4 ) , ( ) => Array ( n ) . fill ( 0 ) ) ; if ( arr [ 0 ] == 0 ) dp [ 0 ] [ 0 ] = 1 ; else dp [ 1 ] [ 0 ] = 1 ; for ( var i = 1 ; i < n ; i ++ ) { if ( arr [ i ] == 0 ) dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + 1 ; else dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] ; } for ( var i = 1 ; i < n ; i ++ ) { if ( arr [ i ] == 1 ) dp [ 1 ] [ i ] = Math . max ( dp [ 1 ] [ i - 1 ] + 1 , dp [ 0 ] [ i - 1 ] + 1 ) ; else dp [ 1 ] [ i ] = dp [ 1 ] [ i - 1 ] ; } for ( var i = 1 ; i < n ; i ++ ) { if ( arr [ i ] == 0 ) { dp [ 2 ] [ i ] = Math . max ( dp [ 2 ] [ i - 1 ] + 1 , Math . max ( dp [ 1 ] [ i - 1 ] + 1 , dp [ 0 ] [ i - 1 ] + 1 ) ) ; } else dp [ 2 ] [ i ] = dp [ 2 ] [ i - 1 ] ; } for ( var i = 1 ; i < n ; i ++ ) { if ( arr [ i ] == 1 ) { dp [ 3 ] [ i ] = Math . max ( dp [ 3 ] [ i - 1 ] + 1 , Math . max ( dp [ 2 ] [ i - 1 ] + 1 , Math . max ( dp [ 1 ] [ i - 1 ] + 1 , dp [ 0 ] [ i - 1 ] + 1 ) ) ) ; } else dp [ 3 ] [ i ] = dp [ 3 ] [ i - 1 ] ; } var ans = Math . max ( dp [ 2 ] [ n - 1 ] , Math . max ( dp [ 1 ] [ n - 1 ] , Math . max ( dp [ 0 ] [ n - 1 ] , dp [ 3 ] [ n - 1 ] ) ) ) ; document . write ( ans ) ; } var n = 4 ; var arr = [ 0 , 1 , 0 , 1 ] ; main_fun ( arr , n ) ;