AlgoViz
HomeDynamic Programming

Number of Longest Increasing Subsequences

Medium

Carry a count alongside each length

Problem

Count how many distinct longest increasing subsequences an array has.

In simple words

Track both the longest increasing length ending at each index and how many ways achieve it.

The idea

Store both the LIS length ending at each index and how many such subsequences there are. A strictly longer predecessor resets the count, while an equal-length one adds to it — that distinction is the whole problem.

The trick

  • Longer predecessor: copy its count. Equal: add to the count.
  • Sum the counts across all indices achieving the maximum length.
  • O(n²).
2
5
3
7
101
18
0
1
2
3
4
5

Step 1 of 8. Keep the smallest tail for each length. Binary-search each number into "tails". Values: 2, 5, 3, 7, 101, 18.

1/8
Optimal
timeO(n log n)spaceO(n)

Replace the first tail ≥ x.

1// keep the smallest possible tail for each length2const tails = [];3for (const x of nums) {4  let lo = 0, hi = tails.length;5  while (lo < hi) { const m=(lo+hi)>>1;6    if (tails[m] < x) lo = m+1; else hi = m; }7  tails[lo] = x;8}9return tails.length;

Input

array
[2, 5, 3, 7, 101, 18]

Memory

num
—

Output

LIS
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 3, 5, 4, 7]
Output:
2
Explanation:
Two different length-4 increasing runs.

Example 2

Input:
nums = [2, 2, 2, 2]
Output:
4
Explanation:
Each 2 is its own length-1 run → 4.

Example 3

Input:
nums = [1, 2, 3]
Output:
1
Explanation:
One increasing run.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.