# LeetCode 673: Number of Longest Increasing Subsequence

## Problem Restatement

We are given an integer array `nums`.

We need to return the number of longest increasing subsequences.

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

The subsequence must be strictly increasing. Equal adjacent values do not count as increasing. The official problem statement asks for the number of longest increasing subsequences and notes that the sequence must be strictly increasing.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Number of longest increasing subsequences |
| Subsequence rule | Keep original order, but may skip elements |
| Increasing rule | Each next value must be strictly greater |
| Count rule | Count all subsequences whose length equals the maximum LIS length |

Example function shape:

```python
def findNumberOfLIS(nums: list[int]) -> int:
    ...
```

## Examples

Consider:

```python
nums = [1, 3, 5, 4, 7]
```

The longest increasing subsequences have length `4`.

They are:

```text
1, 3, 5, 7
1, 3, 4, 7
```

So the answer is:

```python
2
```

Another example:

```python
nums = [2, 2, 2, 2, 2]
```

Since the sequence must be strictly increasing, no pair of equal values can be used together.

So the longest increasing subsequence length is `1`.

Each single element is one valid subsequence.

There are five such subsequences, so the answer is:

```python
5
```

## First Thought: Generate All Subsequences

A direct solution is to generate every subsequence, check whether it is strictly increasing, and track the longest length and count.

This is too slow.

An array of length `n` has:

```text
2^n
```

subsequences.

We need to avoid enumerating them.

## Key Insight

This is a longest increasing subsequence problem, but we need both:

1. The best length.
2. The number of ways to achieve that length.

For each index `i`, store two values:

| Array | Meaning |
|---|---|
| `length[i]` | Length of the longest increasing subsequence ending at `nums[i]` |
| `count[i]` | Number of longest increasing subsequences ending at `nums[i]` |

Every element can stand alone, so initially:

```python
length[i] = 1
count[i] = 1
```

Then for every earlier index `j < i`, if:

```python
nums[j] < nums[i]
```

we can append `nums[i]` after a subsequence ending at `j`.

## Dynamic Programming Transition

For each pair `j < i` where `nums[j] < nums[i]`, the candidate length is:

```python
length[j] + 1
```

There are two cases.

If this candidate is longer than the current best ending at `i`, replace the best:

```python
length[i] = length[j] + 1
count[i] = count[j]
```

If this candidate has the same length as the current best, add the number of ways:

```python
count[i] += count[j]
```

This works because each valid subsequence ending at `j` can be extended by `nums[i]`.

## Algorithm

1. Let `n = len(nums)`.
2. Create:
   - `length = [1] * n`
   - `count = [1] * n`
3. For each index `i`:
   - Look at every previous index `j`.
   - If `nums[j] < nums[i]`, try to extend subsequences ending at `j`.
4. After filling the arrays:
   - Find `max_length = max(length)`.
   - Sum `count[i]` for every index where `length[i] == max_length`.
5. Return that sum.

## Correctness

For each index `i`, `length[i]` records the length of the longest strictly increasing subsequence that ends at `nums[i]`.

The initialization is correct because every element alone forms an increasing subsequence of length `1`.

When `nums[j] < nums[i]`, every increasing subsequence ending at `j` can be extended by `nums[i]`. This gives subsequences ending at `i` with length `length[j] + 1`.

If this length is greater than the current `length[i]`, the algorithm replaces the previous best and copies `count[j]`, because all previous shorter endings at `i` are no longer longest for index `i`.

If this length equals the current `length[i]`, the algorithm adds `count[j]`, because it has found additional distinct subsequences ending at `i` with the same best length.

The algorithm considers every earlier valid predecessor `j`, so after processing all pairs, each `length[i]` and `count[i]` is correct.

Every longest increasing subsequence in the full array ends at some index `i` where `length[i]` equals the global maximum length. Summing `count[i]` over those indices counts all longest increasing subsequences exactly once.

Therefore, the algorithm returns the correct number.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | For each index, we scan all previous indices |
| Space | `O(n)` | We store length and count arrays |

## Implementation

```python
from typing import List

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        length = [1] * n
        count = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] >= nums[i]:
                    continue

                candidate = length[j] + 1

                if candidate > length[i]:
                    length[i] = candidate
                    count[i] = count[j]
                elif candidate == length[i]:
                    count[i] += count[j]

        max_length = max(length)

        answer = 0

        for i in range(n):
            if length[i] == max_length:
                answer += count[i]

        return answer
```

## Code Explanation

We initialize every element as a subsequence of length `1`:

```python
length = [1] * n
count = [1] * n
```

Then we process each index:

```python
for i in range(n):
```

For every earlier index:

```python
for j in range(i):
```

we check whether `nums[j]` can come before `nums[i]`:

```python
if nums[j] >= nums[i]:
    continue
```

The strict inequality matters. Equal values cannot be part of the same increasing subsequence.

If the pair is valid, the new length is:

```python
candidate = length[j] + 1
```

If this gives a longer subsequence ending at `i`, we replace the current best:

```python
if candidate > length[i]:
    length[i] = candidate
    count[i] = count[j]
```

If it gives another way to reach the same best length, we add the count:

```python
elif candidate == length[i]:
    count[i] += count[j]
```

After all DP states are computed, we find the global LIS length:

```python
max_length = max(length)
```

Then sum the counts for every index that reaches that length:

```python
for i in range(n):
    if length[i] == max_length:
        answer += count[i]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findNumberOfLIS([1, 3, 5, 4, 7]) == 2
    assert s.findNumberOfLIS([2, 2, 2, 2, 2]) == 5

    assert s.findNumberOfLIS([1, 2, 3, 4]) == 1
    assert s.findNumberOfLIS([4, 3, 2, 1]) == 4

    assert s.findNumberOfLIS([1, 2, 4, 3, 5, 4, 7, 2]) == 3
    assert s.findNumberOfLIS([1]) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,3,5,4,7]` | Standard example with two LIS |
| `[2,2,2,2,2]` | Strict increasing rule makes each single element valid |
| Already increasing | Only one LIS using all elements |
| Strictly decreasing | Every single element is an LIS |
| Mixed values | Checks accumulation from multiple predecessors |
| Single element | Smallest valid input |