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}

见题面

见题面