Dynamic Programming • Extensions

Number of LIS

Not just finding the length of the Longest Increasing Subsequence, but finding HOW MANY subsequences have that maximum length.

Try Interactive Simulator

Overview

This builds directly on the standard LIS O(N^2) solution. Instead of just maintaining an array `dp` for lengths, we introduce a second array `count`.

The Count Array

`count[i]` represents the number of longest increasing subsequences that strictly end at index `i`.

Finding a New Max

When extending `dp[j]`, if `dp[j] + 1 > dp[i]`, we found a strictly longer sequence. We update `dp[i]` and INHERIT the count from `j`: `count[i] = count[j]`.

Tying a Max

If `dp[j] + 1 == dp[i]`, we found another distinct way to form a sequence of the current max length. We ADD the counts: `count[i] += count[j]`.

1

3

5

4

7

Length (dp)

1

Ways (count)

1

Code Tracker

:::

1if (nums[i] > nums[j]) {

2 if (dp[j] + 1 > dp[i]) {

3 dp[i] = dp[j] + 1;

4 count[i] = count[j]; // New max length, reset count to j's count

5 } else if (dp[j] + 1 === dp[i]) {

6 count[i] += count[j]; // Same max length, add j's ways

7 }

8}

Number Of Lis

Number Of Lis

Number of LIS

Overview

The Count Array

Finding a New Max

Tying a Max

Number of LIS

Overview

The Count Array

Finding a New Max

Tying a Max