Number of sub | Java implementation of above 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
public class GFG { static int N = 10000 ; static int count_required_sequence ( int n , int arr [ ] ) { int total_required_subsequence = 0 ; int total_n_required_subsequence = 0 ; int [ ] [ ] dp = new int [ N ] [ 2 ] ; for ( int i = 0 ; i < n ; i ++ ) { int turn_required = 0 ; for ( int j = - 1 ; j <= 1 ; j ++ ) turn_required += dp [ arr [ i ] + j ] [ 0 ] ; int required_end_i = ( total_required_subsequence + turn_required ) ; int 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 ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 6 , 2 , 1 , 9 } ; int n = arr . length ; System . out . println ( count_required_sequence ( n , arr ) ) ; } }