---

1. Problem Summary

You are given an integer array nums.
Your task is to determine:

1. The length of the longest increasing subsequence (LIS)
2. The number of distinct subsequences in the array that have that maximum length

Important clarifications:

• A subsequence is formed by deleting zero or more elements without changing order.
• Increasing means strictly increasing (nums[i] < nums[j]).
• Multiple subsequences may share values but are counted separately if their index selections differ.
• You must return only the count of such longest subsequences.

Example:

nums = [1,3,5,4,7]
Longest increasing subsequences have length 4:
[1,3,5,7]
[1,3,4,7]
Count = 2

---

2. Key Insights

LIS length alone is not enough

This problem extends the classic LIS by also counting how many achieve that length.

We track two values per index

For each index i:

1. length[i] = length of LIS ending at i
2. count[i] = number of LIS sequences that end at i

Transition logic

For every earlier index j < i:

• If nums[j] < nums[i], then nums[i] can extend nums[j]

Cases:

1. If length[j] + 1 > length[i]
   → found a longer subsequence ending at i
   Update: length[i] = length[j] + 1 count[i] = count[j]
2. If length[j] + 1 == length[i]
   → found another subsequence of same max length ending at i
   Update: count[i] += count[j]

Final answer

Find maximum LIS length maxLen, then sum all counts where:

length[i] == maxLen

---

3. Approach

Dynamic Programming with counting

Steps:

1. Initialize length[i] = 1 for all i (each number alone)
2. Initialize count[i] = 1 for all i (each number forms one LIS of length 1)
3. Iterate through all pairs j < i to update transitions
4. Track global max length
5. Sum counts for entries whose length equals max length
6. Return that sum

---

4. Time and Space Complexity

Time Complexity: O(N²)

Nested comparison of all pairs.

Space Complexity: O(N)

Two arrays of size N.

---

5. Java Solution

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        int[] length = new int[n];
        int[] count = new int[n];

        for (int i = 0; i < n; i++) {
            length[i] = 1;
            count[i] = 1;
        }

        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {

                    if (length[j] + 1 > length[i]) {
                        length[i] = length[j] + 1;
                        count[i] = count[j];
                    } else if (length[j] + 1 == length[i]) {
                        count[i] += count[j];
                    }
                }
            }
            maxLen = Math.max(maxLen, length[i]);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            if (length[i] == maxLen) {
                result += count[i];
            }
        }

        return result;
    }
}

---

6. Dry Run Examples

Example 1

Input:

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

Initialize:
length = [1,1,1,1,1]
count = [1,1,1,1,1]

Process:

i=1 (3):
extends 1 → length[1]=2, count[1]=1

i=2 (5):
extends 1 → temp length=2, count=1
extends 3 → length becomes 3, count=1
length=[1,2,3,1,1], count=[1,1,1,1,1]

i=3 (4):
extends 1 → temp len=2
extends 3 → temp len=3
cannot extend 5
so length=3, count=1

i=4 (7):
extends 1 → len=2
extends 3 → len=3
extends 5 → len=4, count=1
extends 4 → same len=4, count becomes 2

Final:
longest length = 4
count = 2

Output:

2

---

Example 2

Input:

nums = [2,2,2,2,2]

No number can extend another because values equal.

length = [1,1,1,1,1]
count = [1,1,1,1,1]
maxLen = 1
sum counts = 5

Output:

5

---

Example 3

Input:

nums = [1,2,4,3,5,4,7,2]

Final LIS length = 4
Number of sequences = 3

Output:

3

---

7. Why This Solution Works

• Tracks both LIS length and number of ways
• Correctly aggregates counts across equal-length paths
• Handles duplicates properly
• Builds solutions incrementally
• Proven DP formulation

---

8. Common Mistakes

1. Returning length instead of count
2. Forgetting to reset count when longer length found
3. Summing counts incorrectly
4. Assuming strictly monotonic array
5. Confusing subsequence with substring (must respect order but not contiguity)