The idea is to use two arrays `len[n]`

and `cnt[n]`

to record the maximum length of Increasing Subsequence and the coresponding number of these sequence which ends with `nums[i]`

, respectively. That is:

`len[i]`

: the length of the Longest Increasing Subsequence which ends with `nums[i]`

.

`cnt[i]`

: the number of the Longest Increasing Subsequence which ends with `nums[i]`

.

Then, the result is the sum of each `cnt[i]`

while its corresponding `len[i]`

is the maximum length.

Java version:

```
public int findNumberOfLIS(int[] nums) {
int n = nums.length, res = 0, max_len = 0;
int[] len = new int[n], cnt = new int[n];
for(int i = 0; i<n; i++){
len[i] = cnt[i] = 1;
for(int j = 0; j <i ; j++){
if(nums[i] > nums[j]){
if(len[i] == len[j] + 1)cnt[i] += cnt[j];
if(len[i] < len[j] + 1){
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
}
if(max_len == len[i])res += cnt[i];
if(max_len < len[i]){
max_len = len[i];
res = cnt[i];
}
}
return res;
}
```

C++ version: (use `vector<pair<int, int>> dp`

to combine `len[]`

and `cnt[]`

)

```
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size(), res = 0, max_len = 0;
vector<pair<int,int>> dp(n,{1,1}); //dp[i]: {length, number of LIS which ends with nums[i]}
for(int i = 0; i<n; i++){
for(int j = 0; j <i ; j++){
if(nums[i] > nums[j]){
if(dp[i].first == dp[j].first + 1)dp[i].second += dp[j].second;
if(dp[i].first < dp[j].first + 1)dp[i] = {dp[j].first + 1, dp[j].second};
}
}
if(max_len == dp[i].first)res += dp[i].second;
if(max_len < dp[i].first){
max_len = dp[i].first;
res = dp[i].second;
}
}
return res;
}
```