Introduction

Number of LIS is an advanced variation of the Longest Increasing Subsequence problem.

Instead of finding:

Length of LIS

we need to find:

How many LIS exist.

Example

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

Output:

2

Explanation:

LIS #1
[1,3,5,7]

LIS #2
[1,3,4,7]

Total:

2

Key Observation

For every index:

Track:Length and Count

Two DP arrays:

length[i] = Length of LIS ending at i

Recurrence

If:

nums[j] < nums[i]

and we find a longer sequence:

length[j] + 1 > length[i]

Then:

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

If we find another LIS of same length:

length[j] + 1 == length[i]

Then:

count[i] += count[j]

Dry Run

Input:

[1,3,5,4,7]

Length Array:

[1,2,3,3,4]

Count Array:

[1,1,1,1,2]

Maximum Length:

4

Answer:

2

Approach : Dynamic Programming

Explanation

For each element:

  1. Check all previous elements.
  2. Extend increasing subsequences.
  3. Update length array.
  4. Update count array.
  5. Sum counts having maximum LIS length.

Practice

Complexity Analysis

Dynamic ProgrammingTime Complexity: O(n²)
Space Complexity: O(n)

Why This Problem is Important

  • LIS Variations
  • Counting DP
  • Sequence DP
  • Multiple DP Arrays
  • State Transitions

Common Beginner Mistakes

  • Tracking only length
  • Forgetting count array
  • Incorrect count updates
  • Summing all counts
  • Ignoring equal-length LIS

Interview Tip

Always explain:

length[i] stores LIS lengthcount[i] stores number of LIS

When another LIS of same length is found:

count[i] += count[j]

This is the core interview insight.

Related Questions

  • Longest Increasing Subsequence
  • Russian Doll Envelopes
  • Largest Divisible Subset
  • Longest Bitonic Subsequence
  • Maximum Length Pair Chain

Final Takeaway

Number of LIS extends the classic LIS problem by counting how many longest subsequences exist.

It teaches:

  • Counting DP
  • Multiple State Arrays
  • Sequence DP
  • State Transitions

Mastering Number of LIS helps solve advanced sequence-based Dynamic Programming interview questions.