# Number Of Longest Increasing Subsequence Problem

## Description

LeetCode Problem 673.

Given an integer arraynums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

``````1
2
3
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
``````

Example 2:

``````1
2
3
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
``````

Constraints:

• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
const int n = nums.size();
// stores length of longest sequence till i-th position
vector<int> lis(n,1);
// stores count of longest sequence of length lis[i]
vector<int> count(n,1);
// maximum length of lis
int maxLen = 1;

for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (lis[j] + 1 > lis[i]) {
// strictly increasing
lis[i] = lis[j] + 1;
count[i] = count[j];
}
// this means there are more subsequences of same length ending at length lis[i]
else if (lis[j] + 1 == lis[i]) {
count[i] += count[j];
}
}
}
maxLen = max(maxLen, lis[i]);
}

int numOfLIS = 0;
// count all the subseq of length maxLen
for (int i = 0; i < n; i++) {
if (lis[i] == maxLen)
numOfLIS += count[i];
}

return numOfLIS;
}
};
``````