# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-lis/673.-number-of-longest-increasing-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.