The O(n) Club: Number of Longest Increasing Subsequence — Now With Extra Counting!

The O(n) Club: Number of Longest Increasing Subsequence — Now With Extra Counting!

⚡ TL;DR

This isn’t just “find the LIS length.” It’s “find how many Olympic-level increasing sequences you have.” Brute force? Only if you hate time. The punchy O(n²) dynamic programming (DP) approach looks like this in Java:

int[] length = new int[n];
int[] count = new int[n];
Arrays.fill(length, 1);
Arrays.fill(count, 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];
      }
// sum count[i] for all i with max length

🧠 How Devs Usually Mess This Up

Classic mistake? Copy-paste your favorite O(n log n) LIS code and wait for the confetti. Except…no confetti, just “Wrong Answer.” Why? O(n log n) finds the length of the LIS. Counting how many? You’ll need to actually track that. Many folks also forget to sync up the length and count updates—increasing your odds of double-counting faster than your caffeine intake.

🔍 What’s Actually Going On

Pretend each number is a rickety ladder rung. You’re climbing, and for every new rung (index), you want to know:

🛠️ PseudoCode

• Start: length[i] = 1, count[i] = 1 for all i. Every number is at least a solo rock band.
• For each i:
  • Loop j = 0 to i-1:
  • 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]: