Number of Longest Increasing Subsequence

medium array dp segment tree

Problem

Given an integer array nums, return the number of longest strictly increasing subsequences.

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

Output2

The two LIS of length 4 are [1,3,4,7] and [1,3,5,7].

nums (comma-separated)

def find_number_of_lis(nums):
    n = len(nums)
    length = [1] * n
    count = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    best = max(length)
    return sum(c for l, c in zip(length, count) if l == best)

function findNumberOfLIS(nums) {
  const n = nums.length;
  const length = new Array(n).fill(1), count = new Array(n).fill(1);
  for (let i = 0; i < n; i++) {
    for (let 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];
      }
    }
  }
  const best = Math.max(...length);
  return length.reduce((s, l, k) => s + (l === best ? count[k] : 0), 0);
}

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, best = 0, ans = 0;
        int[] length = new int[n], 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];
            }
            best = Math.max(best, length[i]);
        }
        for (int i = 0; i < n; i++) if (length[i] == best) ans += count[i];
        return ans;
    }
}

int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size(), best = 0, ans = 0;
    vector<int> length(n, 1), count(n, 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];
        }
        best = max(best, length[i]);
    }
    for (int i = 0; i < n; i++) if (length[i] == best) ans += count[i];
    return ans;
}

Explanation

This is the classic Longest Increasing Subsequence problem with a twist: we don't just want the longest length, we want how many increasing subsequences hit that length. The fix is to track two arrays side by side: length[i] = the longest increasing subsequence ending at index i, and count[i] = how many such best subsequences end there.

Both arrays start at 1, since each element alone is a subsequence of length 1 with one way to form it.

For each i we look back at every earlier j with nums[j] < nums[i]. If extending through j gives a strictly longer subsequence (length[j] + 1 > length[i]), we found a new best, so we copy count[i] = count[j]. If it ties the current best (length[j] + 1 == length[i]), we add count[i] += count[j] because those are additional distinct ways.

Example: nums = [1, 3, 5, 4, 7]. The longest length is 4, reached by both [1,3,4,7] and [1,3,5,7], so the answer is 2.

Finally we find the global best length and sum the count values at every index whose length equals it. The nested loop makes this O(n^2).

Time: O(n^2) Space: O(n)