Number of sub | Javascript implementation of the approach ; Function to return the number of subsequences which have at least one consecutive pair with difference less than or equal to 1 ; Not required sub - sequences which turn required on adding i ; Required sub - sequence till now will be required sequence plus sub - sequence which turns required ; Similarly for not required ; Also updating total required and not required sub - sequences ; Also , storing values in dp ; Driver code
var N = 10000 ; function count_required_sequence ( n , arr ) { var total_required_subsequence = 0 ; var total_n_required_subsequence = 0 ; var dp = Array . from ( Array ( N ) , ( ) => Array ( 2 ) . fill ( 0 ) ) ; for ( var i = 0 ; i < n ; i ++ ) { var turn_required = 0 ; for ( var j = - 1 ; j <= 1 ; j ++ ) turn_required += dp [ arr [ i ] + j ] [ 0 ] ; var required_end_i = ( total_required_subsequence + turn_required ) ; var n_required_end_i = ( 1 + total_n_required_subsequence - turn_required ) ; total_required_subsequence += required_end_i ; total_n_required_subsequence += n_required_end_i ; dp [ arr [ i ] ] [ 1 ] += required_end_i ; dp [ arr [ i ] ] [ 0 ] += n_required_end_i ; } return total_required_subsequence ; } var arr = [ 1 , 6 , 2 , 1 , 9 ] ; var n = arr . length ; document . write ( count_required_sequence ( n , arr ) + " " ) ;