> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-lis/673.-number-of-longest-increasing-subsequence.md).

# 673. Number of Longest Increasing Subsequence

## Problem Statement

<br>

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

**Notice** that the sequence has to be **strictly** increasing.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,3,5,4,7]
</strong><strong>Output: 2
</strong><strong>Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [2,2,2,2,2]
</strong><strong>Output: 5
</strong><strong>Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 2000`
* `-106 <= nums[i] <= 106`\ <br>

## Intuition

```
Maintain a count array to keep count along with the dp array

Logic is, when you get the same 1 + dp[prev] == dp[index]
Means you got the sequence count again 
So you incr the count of the count array
```

### Links

<https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/>

### Video Links

<https://www.youtube.com/watch?v=cKVl1TFdNXg&t=1004s&ab_channel=takeUforward>

### Approach 1:

```
Maintain dp & count array
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        vector<int> ct(n,1);
        int count = 1;
        int maxi = 1;

        for(int index=1; index<n; index++){
            for(int prev=0; prev<index; prev++){

                if(nums[prev] < nums[index] and 1+dp[prev] > dp[index]){
                    dp[index] = 1+dp[prev];
                    ct[index] = ct[prev];
                }

                else if(nums[prev] < nums[index] and 1+dp[prev] == dp[index])
                    ct[index] += ct[prev];
            }

            maxi = max( maxi, dp[index]);
        }

        int nos = 0;
        // sum of all the count having seq as maxi
        // LIS can be at different position

        for(int i=0; i<n; i++){
            if(dp[i]==maxi)
                nos += ct[i];
        }

        return nos;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###