# Number of Longest Increasing Subsequence LeetCode Solution

## Problem Description

The **Number of Longest Increasing Subsequence LeetCode Solution** problem involves finding the number of longest increasing subsequences in an array. Given an unsorted array of integers, the task is to find the length of the longest increasing subsequence and the number of such subsequences with that maximum length.

## Intuition

The problem can be approached using dynamic programming. We can maintain two arrays: `length`

to store the length of the longest increasing subsequence ending at each index, and `count`

to store the number of such subsequences. We iterate through the array, updating these arrays based on the increasing subsequence conditions.

## Solution Approach

- Initialize two arrays:
`length`

of size`n`

(length of the input array) and`count`

of size`n`

, both initialized to 1. - Iterate through the array with two nested loops. For each pair of indices (i, j) where
`nums[i] < nums[j]`

, update`length[j]`

and`count[j]`

based on the conditions. - Find the maximum length in the
`length`

array. - Iterate through the
`length`

array and accumulate the counts of subsequences with maximum length. - Return the maximum length and the count of such subsequences.

## Example Walkthrough

Consider the following array: `[1, 3, 5, 4, 7]`

- Initialize
`length`

and`count`

arrays:`[1, 1, 1, 1, 1]`

and`[1, 1, 1, 1, 1]`

. - Iterate through the array:
- For
`nums[1] = 3`

, update`length[1]`

to 2 and`count[1]`

to 1. - For
`nums[2] = 5`

, update`length[2]`

to 3 and`count[2]`

to 1. - For
`nums[3] = 4`

, update`length[3]`

to 3 and`count[3]`

to 1. - For
`nums[4] = 7`

, update`length[4]`

to 4 and`count[4]`

to 2.

- For
- Find the maximum length, which is 4.
- Accumulate counts of subsequences with length 4, which is 2.
- Return the maximum length (4) and the count (2).

## Code Solutions

```
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
lengths = [1] * n
counts = [1] * n
for j in range(n):
for i in range(j):
if nums[i] < nums[j]:
if lengths[i] + 1 > lengths[j]:
lengths[j] = lengths[i] + 1
counts[j] = counts[i]
elif lengths[i] + 1 == lengths[j]:
counts[j] += counts[i]
max_length = max(lengths)
result = sum(count for length, count in zip(lengths, counts) if length == max_length)
return result
```

```
class Solution {
public:
int findNumberOfLIS(vector
```& nums) {
if (nums.empty())
return 0;
int n = nums.size();
vector lengths(n, 1);
vector counts(n, 1);
for (int j = 0; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
if (lengths[i] + 1 > lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
}
int maxLength = *max_element(lengths.begin(), lengths.end());
int result = 0;
for (int k = 0; k < n; k++) {
if (lengths[k] == maxLength)
result += counts[k];
}
return result;
}
};

```
class Solution {
public int findNumberOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int n = nums.length;
int[] lengths = new int[n];
int[] counts = new int[n];
Arrays.fill(lengths, 1);
Arrays.fill(counts, 1);
for (int j = 0; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
if (lengths[i] + 1 > lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
}
int maxLength = Arrays.stream(lengths).max().orElse(0);
int result = 0;
for (int k = 0; k < n; k++) {
if (lengths[k] == maxLength)
result += counts[k];
}
return result;
}
}
```

## Time and Space Complexity

Time Complexity: O(n^2) – Two nested loops are used to iterate through the array.

Space Complexity: O(n) – Additional arrays `lengths`

and `counts`

of size `n`

are used.