Count all increasing subsequences | Function To Count all the sub - sequences possible in which digit is greater than all previous digits arr [ ] is array of n digits ; count [ ] array is used to store all sub - sequences possible using that digit count [ ] array covers all the digit from 0 to 9 ; scan each digit in arr [ ] ; count all possible sub - sequences by the digits less than arr [ i ] digit ; store sum of all sub - sequences plus 1 in count [ ] array ; Now sum up the all sequences possible in count [ ] array ; Driver Code
def countSub ( arr , n ) : NEW_LINE INDENT count = [ 0 for i in range ( 10 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( arr [ i ] - 1 , - 1 , - 1 ) : NEW_LINE INDENT count [ arr [ i ] ] += count [ j ] NEW_LINE DEDENT count [ arr [ i ] ] += 1 NEW_LINE DEDENT result = 0 NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT result += count [ i ] NEW_LINE DEDENT return result NEW_LINE DEDENT arr = [ 3 , 2 , 4 , 5 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE print ( countSub ( arr , n ) ) NEW_LINE