Number of sub | Python3 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
import numpy as np ; NEW_LINE N = 10000 ; NEW_LINE def count_required_sequence ( n , arr ) : NEW_LINE INDENT total_required_subsequence = 0 ; NEW_LINE total_n_required_subsequence = 0 ; NEW_LINE dp = np . zeros ( ( N , 2 ) ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT turn_required = 0 ; NEW_LINE for j in range ( - 1 , 2 , 1 ) : NEW_LINE INDENT turn_required += dp [ arr [ i ] + j ] [ 0 ] ; NEW_LINE DEDENT required_end_i = ( total_required_subsequence + turn_required ) ; NEW_LINE n_required_end_i = ( 1 + total_n_required_subsequence - turn_required ) ; NEW_LINE total_required_subsequence += required_end_i ; NEW_LINE total_n_required_subsequence += n_required_end_i ; NEW_LINE dp [ arr [ i ] ] [ 1 ] += required_end_i ; NEW_LINE dp [ arr [ i ] ] [ 0 ] += n_required_end_i ; NEW_LINE DEDENT return total_required_subsequence ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 6 , 2 , 1 , 9 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( count_required_sequence ( n , arr ) ) ; NEW_LINE DEDENT