Given an array of digits (values lie in range from 0 to 9). The task is to count all the sub sequences possible in array such that in each subsequence every digit is greater than its previous digits in the subsequence.
 
Example 1:
Input : 
a[] = {1, 2, 3, 4}
Output: 
15
Explanation :
There are total increasing subsequences
{1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4},
{2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4},
{1,3,4}, {2,3,4}, {1,2,3,4}
 
Example 2:
Input : 
a[] = {4, 3, 6, 5}
Output:
8
Explanation :
Sub-sequences are {4}, {3}, {6}, {5},
{4,6}, {4,5}, {3,6}, {3,5}
 
Example 3:
Input : 
a[] = {3, 2, 4, 5, 4}
Output : 
14
Explanation :
Sub-sequences are {3}, {2}, {4}, {3,4},
{2,4}, {5}, {3,5}, {2,5}, {4,5}, {3,2,5}
{3,4,5}, {4}, {3,4}, {2,4}
Your Task:
You don't have to print anything, printing is done by the driver function. You have to complete the function countSub() which takes the array a[] and its size N as inputs and returns the count of all increasing subsequences in given array of digits.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O( max(a[i]) ) = O(10)
Constraints: 
1 ≤ N ≤ 500
1 ≤ a[i] ≤ 9

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def countSub(self, arr, n):
        # Your code goes here

Solutions:
class Solution:

	def countSub(self, arr, n):
		count = [0 for i in range(10)]
		for i in range(n):
			for j in range(arr[i] - 1, -1, -1):
				count[arr[i]] += count[j]
			count[arr[i]] += 1
		result = 0
		for i in range(10):
			result += count[i]
		return result


class Solution:

	def countSub(self, arr, n):
		dgts = [0] * 10
		for i in range(n):
			for j in range(arr[i] - 1, -1, -1):
				dgts[arr[i]] += dgts[j]
			dgts[arr[i]] += 1
		ans = 0
		for i in dgts:
			ans += i
		return ans


class Solution:

	def countSub(self, arr, n):
		ct = [0 for x in range(10)]
		for i in range(n):
			for j in range(arr[i] - 1, -1, -1):
				ct[arr[i]] += ct[j]
			ct[arr[i]] += 1
		res = 0
		for i in range(10):
			res += ct[i]
		return res


class Solution:

	def countSub(self, arr, n):
		count = [0] * 10
		for i in range(n):
			for j in range(arr[i] - 1, -1, -1):
				count[arr[i]] += count[j]
			count[arr[i]] += 1
		return sum(count)

class Solution1:

	def countSub(self, arr, n):
		dp = [1] * n
		total_sum = 1
		for i in range(1, n):
			for j in range(i + 1):
				if arr[j] < arr[i]:
					dp[i] += dp[j]
			total_sum += dp[i]
		return total_sum


class Solution:

	def solve(self, arr, i, prev, dp):
		if i >= len(arr):
			return 1
		if (i, prev) in dp:
			return dp[i, prev]
		if arr[i] > prev:
			dp[i, prev] = self.solve(arr, i + 1, arr[i], dp) + self.solve(arr, i + 1, prev, dp)
			return dp[i, prev]
		else:
			dp[i, prev] = self.solve(arr, i + 1, prev, dp)
			return dp[i, prev]

	def countSub(self, arr, n):
		dp = {}
		return self.solve(arr, 0, -1, dp) - 1


class Solution:

	def countSub(self, arr, n):
		l = [0] * 10
		for i in range(n):
			l[arr[i]] += 1
			for j in range(arr[i]):
				l[arr[i]] += l[j]
		return sum(l)


class Solution:

	def countSub(self, arr, n):
		c = [0 for i in range(10)]
		for i in range(n):
			for j in range(arr[i] - 1, -1, -1):
				c[arr[i]] += c[j]
			c[arr[i]] += 1
		r = 0
		for i in range(10):
			r += c[i]
		return r


class Solution:

	def countSub(self, arr, n):
		cnt = [0] * n
		cnt[0] = 1
		ans = 1
		for i in range(1, n):
			s1 = arr[i]
			s = 0
			for j in range(0, i):
				if s1 > arr[j]:
					s += cnt[j]
			cnt[i] = s + 1
		return sum(cnt)


class Solution:

	def countSub(self, arr, n):
		mx = max(arr)
		count = [0 for i in range(mx + 1)]
		for i in range(n):
			for j in range(arr[i] - 1, -1, -1):
				count[arr[i]] += count[j]
			count[arr[i]] += 1
		res = 0
		for i in count:
			res += i
		return res


class Solution:

	def countSub(self, arr, n):
		l1 = [0] * n
		l1[0] = 1
		for i in range(1, n):
			s1 = arr[i]
			su = 0
			for j in range(0, i):
				if s1 > arr[j]:
					su += l1[j]
			l1[i] = su + 1
		return sum(l1)


class Solution:

	def countSub(self, arr, n):
		dp = [0] * n
		dp[0] = 1
		for i in range(1, n):
			x = arr[i]
			count = 0
			for j in range(0, i):
				if x > arr[j]:
					count = count + dp[j]
			dp[i] = count + 1
		return sum(dp)


class Solution:

	def countSub(self, arr, n):
		digit = [0] * 10
		for i in arr:
			temp = sum(digit[:i])
			digit[i] = digit[i] + temp + 1
		return sum(digit)


class Solution:

	def countSub(self, arr, n):
		d = {}
		for i in range(0, n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
			for j in range(0, 10):
				if j < arr[i] and j in d:
					d[arr[i]] += d[j]
		c = 0
		for x in d.values():
			c += x
		return c


class Solution:

	def countSub(self, arr, n):
		count = [0 for i in range(10)]
		for i in range(n):
			for j in range(arr[i] - 1, -1, -1):
				count[arr[i]] += count[j]
			count[arr[i]] += 1
		return sum(count)

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.countSub(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def countSub(self, arr, n):
		maxim = max(arr)
		add = [0] * (maxim + 1)
		ans = 0
		for i in range(n):
			add[arr[i]] = add[arr[i]] + 1
			for j in range(arr[i]):
				add[arr[i]] = add[arr[i]] + add[j]
		for i in range(maxim + 1):
			ans = ans + add[i]
		return ans