Given an integer array arr, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Example:
Input:
n = 5
arr = [1,3,5,4,7]
Output:
2
Explanation:
The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
Your Task:
You don't have to read input or print anything. Your task is to complete the function NumberofLIS() which takes the integer n and array arr and returns the number of the Longest Increasing Subsequences.
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n^{2})
Constraint:
1 <= n <= 2000
1 <= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def NumberofLIS(self, n, arr):

        # Code here

Solutions:
class Solution:

	def NumberofLIS(self, n, nums):
		(res, lis) = (0, 1)
		(dp, cnt) = ([1] * n, [1] * n)
		for i in range(1, n):
			for prev in range(i):
				if nums[prev] < nums[i]:
					if dp[prev] + 1 > dp[i]:
						dp[i] = dp[prev] + 1
						cnt[i] = cnt[prev]
					elif dp[prev] + 1 == dp[i]:
						cnt[i] += cnt[prev]
			lis = max(lis, dp[i])
		for i in range(n):
			if dp[i] == lis:
				res += cnt[i]
		return res


import bisect

class Solution:

	def NumberofLIS(self, n, arr):
		dp = [1] * n
		cnt = [1] * n
		ma = 0
		for i in range(1, n):
			for j in range(i):
				if arr[j] < arr[i]:
					if dp[i] < dp[j] + 1:
						dp[i] = dp[j] + 1
						cnt[i] = cnt[j]
					elif dp[i] == dp[j] + 1:
						cnt[i] += cnt[j]
			ma = max(ma, dp[i])
		return sum((cnt[i] for i in range(n) if dp[i] == ma))


class Solution:

	def NumberofLIS(self, n, a):
		dp = [1] * n
		hash = [1] * n
		maxi = 0
		for ind in range(n):
			for prev in range(ind):
				if a[prev] < a[ind] and 1 + dp[prev] > dp[ind]:
					dp[ind] = 1 + dp[prev]
					hash[ind] = hash[prev]
				elif a[prev] < a[ind] and 1 + dp[prev] == dp[ind]:
					hash[ind] += hash[prev]
			maxi = max(maxi, dp[ind])
		ans = 0
		for i in range(n):
			if dp[i] == maxi:
				ans += hash[i]
		return ans


class Solution:

	def NumberofLIS(self, n, arr):
		dp = [1 for i in range(n)]
		count = [1 for i in range(n)]
		maxi = 1
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j] and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
					count[i] = count[j]
					if maxi < dp[i]:
						maxi = dp[i]
				elif 1 + dp[j] == dp[i]:
					count[i] += count[j]
		ans = 0
		for i in range(n):
			if dp[i] == maxi:
				ans += count[i]
		return ans


class Solution:

	def NumberofLIS(self, n, nums):
		n = len(nums)
		(dp, cnt) = ([1] * n, [1] * n)
		for i in range(n):
			for j in range(i):
				if nums[j] < nums[i]:
					if dp[i] < 1 + dp[j]:
						dp[i] = 1 + dp[j]
						cnt[i] = cnt[j]
					elif dp[i] == 1 + dp[j]:
						cnt[i] += cnt[j]
		return sum((b for (a, b) in zip(dp, cnt) if a == max(dp)))


class Solution:

	def NumberofLIS(self, n, arr):
		dp = [1] * n
		maxi = 1
		cnt = [1] * n
		for idx in range(n):
			for prev in range(idx):
				if arr[prev] < arr[idx] and 1 + dp[prev] > dp[idx]:
					dp[idx] = 1 + dp[prev]
					cnt[idx] = cnt[prev]
				elif arr[prev] < arr[idx] and 1 + dp[prev] == dp[idx]:
					cnt[idx] += cnt[prev]
			maxi = max(maxi, dp[idx])
		nos = 0
		for i in range(n):
			if dp[i] == maxi:
				nos += cnt[i]
		return nos


class Solution:

	def NumberofLIS(self, n, arr):
		dp = [1 for i in range(n)]
		max_ = 0
		count = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if arr[j] < arr[i]:
					if dp[j] + 1 > dp[i]:
						dp[i] = dp[j] + 1
						count[i] = count[j]
					elif dp[j] + 1 == dp[i]:
						count[i] += count[j]
			max_ = max(max_, dp[i])
		ans = 0
		for i in range(n):
			if dp[i] == max_:
				ans += count[i]
		return ans


class Solution:

	def NumberofLIS(self, n, arr):
		dp = [1] * n
		cnt = [1] * n
		maxi = 0
		for i in range(n):
			for j in range(i):
				if arr[j] < arr[i]:
					if 1 + dp[j] > dp[i]:
						dp[i] = 1 + dp[j]
						cnt[i] = cnt[j]
					elif 1 + dp[j] == dp[i]:
						cnt[i] += cnt[j]
			maxi = max(maxi, dp[i])
		ans = 0
		for i in range(n):
			if dp[i] == maxi:
				ans += cnt[i]
		return ans


class Solution:

	def NumberofLIS(self, n, nums):
		n = len(nums)
		dp = [1 for _ in range(n)]
		count = [1 for _ in range(n)]
		c = {}
		for i in range(n):
			for j in range(i):
				if nums[j] < nums[i]:
					if dp[i] == 1 + dp[j]:
						count[i] += count[j]
					elif dp[i] < 1 + dp[j]:
						count[i] = count[j]
						dp[i] = 1 + dp[j]
		res = max(dp)
		ans = 0
		for i in range(n):
			if dp[i] == res:
				ans += count[i]
		return ans


class Solution:

	def NumberofLIS(self, n, nums):
		n = len(nums)
		dp = [1] * n
		cnt = [1] * n
		for idx in range(n):
			for prev_idx in range(idx):
				if nums[prev_idx] < nums[idx] and dp[idx] < 1 + dp[prev_idx]:
					dp[idx] = 1 + dp[prev_idx]
					cnt[idx] = cnt[prev_idx]
				elif nums[prev_idx] < nums[idx] and dp[idx] == 1 + dp[prev_idx]:
					cnt[idx] += cnt[prev_idx]
		maxi = max(dp)
		nos = 0
		for i in range(n):
			if dp[i] == maxi:
				nos += cnt[i]
		return nos


class Solution:

	def NumberofLIS(self, n, arr):
		lis = [1] * n
		cnt = [1] * n
		maxlen = 1
		ansidx = -1
		for i in range(1, n):
			for j in range(0, i):
				if arr[j] < arr[i] and lis[i] < 1 + lis[j]:
					lis[i] = 1 + lis[j]
					cnt[i] = cnt[j]
				elif arr[j] < arr[i] and lis[i] == 1 + lis[j]:
					cnt[i] += cnt[j]
			if lis[i] > maxlen:
				maxlen = lis[i]
				idx = i
		ans = 0
		for i in range(0, n):
			if lis[i] == maxlen:
				ans += cnt[i]
		return ans


class Solution:

	def NumberofLIS(self, n, arr):
		maxi = 1
		dp = [[1] * 2 for _ in range(n)]
		for i in range(n):
			for prev in range(i):
				if arr[i] > arr[prev]:
					if dp[i][0] < dp[prev][0] + 1:
						dp[i][0] = dp[prev][0] + 1
						dp[i][1] = dp[prev][1]
					elif dp[i][0] == dp[prev][0] + 1:
						dp[i][1] += dp[prev][1]
			maxi = max(maxi, dp[i][0])
		res = 0
		for (val, freq) in dp:
			if val == maxi:
				res += freq
		return res


class Solution:

	def NumberofLIS(self, n, nums):
		n = len(nums)
		dp = [1] * n
		cnt = [1] * n
		lis = 1
		for ind in range(1, n):
			for prev in range(ind):
				if nums[prev] < nums[ind] and dp[ind] < dp[prev] + 1:
					dp[ind] = dp[prev] + 1
					cnt[ind] = cnt[prev]
				elif nums[prev] < nums[ind] and dp[ind] == dp[prev] + 1:
					cnt[ind] = cnt[ind] + cnt[prev]
			lis = max(lis, dp[ind])
		nos = 0
		for i in range(n):
			if dp[i] == lis:
				nos += cnt[i]
		return nos


class Solution:

	def NumberofLIS(self, n, arr):
		dp = [1] * n
		count = [1] * n
		maxi = 1
		for ind in range(n):
			for prev in range(ind):
				if arr[prev] < arr[ind]:
					if dp[prev] + 1 > dp[ind]:
						dp[ind] = dp[prev] + 1
						count[ind] = count[prev]
					elif dp[prev] + 1 == dp[ind]:
						count[ind] += count[prev]
			maxi = max(maxi, dp[ind])
		return sum([j for (i, j) in zip(dp, count) if i == maxi])


class Solution:

	def NumberofLIS(self, n, arr):
		dp = [1 for _ in range(n)]
		cou = [1 for _ in range(n)]
		maxi = 1
		for i in range(n):
			for j in range(i):
				if arr[i] > arr[j] and dp[j] + 1 > dp[i]:
					dp[i] = dp[j] + 1
					cou[i] = cou[j]
				elif arr[i] > arr[j] and dp[j] + 1 == dp[i]:
					cou[i] += cou[j]
			maxi = max(maxi, dp[i])
		nos = 0
		for i in range(n):
			if maxi == dp[i]:
				nos += cou[i]
		return nos