# 673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

**Example 1:**\\

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

**Example 2:**\\

```
Input: [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.
```

**Note:** Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

{% hint style="info" %}
用兩個1D array紀錄長度和數量。len\[i]代表以nums\[i]結尾的LIS長度，cnt\[i]代表以nums\[i]結尾的LIS數量。初始化的值為1，因為只要數列有數字，至少都有1個長度為1的LIS。
{% endhint %}

```cpp
int findNumberOfLIS(vector<int>& nums) { // time: O(n^2); space: O(n)
    int n = nums.size(), res = 0, maxLen = 0; // initialize to 0 for empty input
    vector<int> len(n, 1), cnt(n, 1);
    // len[i]: the length of LIS ending with nums[i]
    // cnt[i]: the number of LIS with len[i]
    // DP relation: len[i] = max({len[j]}, 0 <= j < i) + 1
    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];
                else if (len[i] < len[j] + 1) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                }
            }
        }
        if (maxLen == len[i]) res += cnt[i];
        else if (maxLen < len[i]) {
            maxLen = len[i];
            res = cnt[i];
        }
    }
    return res;
}
```

{% content-ref url="300.-longest-increasing-subsequence" %}
[300.-longest-increasing-subsequence](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/300.-longest-increasing-subsequence)
{% endcontent-ref %}

{% content-ref url="674.-longest-continuous-increasing-subsequence" %}
[674.-longest-continuous-increasing-subsequence](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/674.-longest-continuous-increasing-subsequence)
{% endcontent-ref %}
