## Algorithm

Problem Name: 673. Number of Longest Increasing Subsequence

Given an integer array `nums`, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

```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:

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

Constraints:

• `1 <= nums.length <= 2000`
• `-106 <= nums[i] <= 106`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int findNumberOfLIS(int* nums, int numsSize) {
int i, j, k, res = 0, max_len = 0;
int *tmp, *len, *cnt;

if (numsSize == 0) return 0;

tmp = calloc(numsSize * 2, sizeof(int));
//assert(tmp);
len = &tmp[0];
cnt = &tmp[numsSize];

for (i = 0; i  <  numsSize; i ++) {
len[i] = cnt[i] = 1;
for (j = 0; j  <  i; j ++) {
if (nums[i] > nums[j]) {
if (len[i] < len[j] + 1) {
// reset the length and count
len[i] = len[j] + 1;
cnt[i] = cnt[j];
} else if (len[i] == len[j] + 1) {
// current summary
cnt[i] += cnt[j];
}
}
}

if (max_len  <  len[i]) {
max_len = len[i];   // reset
res = cnt[i];
} else if (max_len == len[i]) {
res += cnt[i];      // total
}
}

free(tmp);

return res;
}
``````
Copy The Code &

Input

cmd
nums = [1,3,5,4,7]

Output

cmd
2

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int>len(n, 1);
vector<int>cnt(n, 1);
int maxlen = 1, res = 0;
for(int i = 0; i  <  n; i++){
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(len[i] == maxlen> res += cnt[i];
if(len[i] > maxlen){
maxlen = len[i];
res = cnt[i];
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
nums = [1,3,5,4,7]

Output

cmd
2

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int findNumberOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int[] count = new int[nums.length];

int maxVal = 0;
int res = 0;

for (int i = 0; i  <  nums.length; i ++) {
dp[i] = count[i] = 1;
for (int j = 0; j  <  i; j++) {
if (nums[j] < nums[i]) {
if (dp[i] == dp[j] + 1) {
count[i] += count[j];
}
else if (dp[i]  <  dp[j] + 1) {
dp[i] = dp[j] + 1;
count[i] = count[j];
}
}
}

if (dp[i] > maxVal) {
maxVal = dp[i];
res = count[i];
}
else if (dp[i] == maxVal) {
res += count[i];
}
}

return res;
}
}
``````
Copy The Code &

Input

cmd
nums = [2,2,2,2,2]

Output

cmd
5

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findNumberOfLIS = function(nums) {
if (nums.length === 0) return 0;
const len = new Array(nums.length);
const cnt = new Array(nums.length);
let max = 1;
let res=1;
len[0] = 1;
cnt[0] = 1;
for (let i = 1; i  <  nums.length; i++) {
len[i] = 1;
cnt[i] = 1;
for (let j = 0; j  <  i; j++) {
if (nums[j] < nums[i]) {
if (len[j] + 1 > len[i]) {
cnt[i] = cnt[j];
len[i] = len[j] + 1;
} else if (len[j] + 1 === len[i]) {
cnt[i] += cnt[j];
}
}
}
if (len[i] > max) {
max = len[i];
res = cnt[i];
} else if (len[i] === max) {
res += cnt[i];
}
}
return res;
};
``````
Copy The Code &

Input

cmd
nums = [2,2,2,2,2]

Output

cmd
5

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findNumberOfLIS(self, nums):
dp = [[1, 1] for _ in range(len(nums))]
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]:
if dp[i][0] >= dp[j][0]: dp[j] = [dp[i][0] + 1, dp[i][1]]
elif dp[i][0] == dp[j][0] - 1: dp[j][1] += dp[i][1]
dp.sort()
return dp and sum(d[1] for d in dp if d[0] == dp[-1][0]) or 0
``````
Copy The Code &

Input

cmd
nums = [1,3,5,4,7]

Output

cmd
2