☕ DSA Java Articles

Topics › Dynamic Programming › DP on LIS

Number of Longest Increasing Subsequences

Medium TUF ID 780 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an integer array nums, return how many strictly increasing subsequences have the maximum possible length. Two subsequences are different when they use different sets of indices, even if the values they spell are the same.

Constraints (LeetCode 673): 1 ≤ n ≤ 2000, -10^6 ≤ nums[i] ≤ 10^6, and the answer is guaranteed to fit in a 32-bit integer.

Example 1

nums = [1, 3, 5, 4, 7]
answer = 2               // the LIS length is 4: 1 3 5 7 and 1 3 4 7

Example 2

nums = [2, 2, 2, 2, 2]
answer = 5               // the LIS length is 1, and each of the 5 elements is one

Approach 1: Brute force

Intuition. Enumerate every subsequence with a bitmask, keep only the strictly increasing ones, and track two numbers: the best length seen so far and how many subsequences achieved it. A longer one resets the count to 1; an equal one adds 1.

Algorithm.

  1. For every non-empty mask, walk the chosen indices and reject the mask as soon as a value is not larger than the previous one.
  2. For a surviving mask of length len: if len > bestLen, set bestLen = len and count = 1; if len == bestLen, increment count.
  3. Return count.
static int bruteForce(int[] nums) {
    int n = nums.length, bestLen = 0, count = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        int len = 0, prev = Integer.MIN_VALUE;
        boolean ok = true;
        for (int i = 0; i < n && ok; i++) {
            if ((mask & (1 << i)) == 0) continue;
            if (len > 0 && nums[i] <= prev) ok = false;
            prev = nums[i];
            len++;
        }
        if (!ok) continue;
        if (len > bestLen) { bestLen = len; count = 1; }
        else if (len == bestLen) count++;
    }
    return count;
}

Complexity. Time O(2^n · n), space O(1). Fine for checking the other methods on arrays of a dozen elements, hopeless for n = 2000.

Approach 2: Better, LIS DP with counts

Intuition. The standard O(n^2) LIS DP computes len[i], the length of the longest strictly increasing subsequence ending at index i, as 1 + max(len[j]) over earlier j with nums[j] < nums[i]. We extend it with a second array, cnt[i], the number of increasing subsequences of length len[i] that end at i.

Every longest chain ending at i looks like “a chain ending at some j, then nums[i]”. It is a longest chain for i exactly when that j has nums[j] < nums[i] and len[j] + 1 == len[i]. Chains coming through different j differ in their second-to-last index, so they never coincide, and the count is simply the sum of cnt[j] over all such j. While scanning j, two things can happen:

At the end, the overall LIS length is maxLen = max(len[i]), and the answer adds cnt[i] over every index whose len[i] == maxLen, because a longest subsequence can end at any of them.

Algorithm.

  1. For each i, start with len[i] = 1, cnt[i] = 1 (the chain made of nums[i] alone).
  2. For each j < i with nums[j] < nums[i], apply the replace-or-add rule above.
  3. Return the sum of cnt[i] over indices with len[i] == maxLen.
static int better(int[] nums) {
    int n = nums.length, maxLen = 0, total = 0;
    int[] len = new int[n], cnt = new int[n];
    for (int i = 0; i < n; i++) {
        len[i] = 1;
        cnt[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] >= nums[i]) continue;
            if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; cnt[i] = cnt[j]; }  // longer chain: inherit its count
            else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];                    // same length: add its count
        }
        maxLen = Math.max(maxLen, len[i]);
    }
    for (int i = 0; i < n; i++) if (len[i] == maxLen) total += cnt[i];
    return total;
}

Dry run on Example 1:

i 0 1 2 3 4
nums 1 3 5 4 7
len 1 2 3 3 4
cnt 1 1 1 1 2

At i = 4 (value 7), j = 2 (value 5) gives length 4 with count 1, and then j = 3 (value 4) gives the same length, adding 1 more. Only index 4 reaches maxLen = 4, so the answer is 2.

Complexity. Time O(n^2): every pair (j, i) is examined once. Space O(n) for the two arrays. For n = 2000 this is 2 million steps, which is what the problem expects.

Approach 3: Optimal, Fenwick tree over values

Intuition. In Approach 2, the inner loop asks one question about the elements already processed: “among those with a value smaller than nums[i], what is the largest len, and what is the total cnt of the ones achieving it?” That is a prefix query over values, if we index elements by the rank of their value instead of by their position. Processing elements in array order guarantees that only earlier indices are in the structure.

A Fenwick (binary indexed) tree can answer it in O(log n) if the thing it stores can be merged associatively. Here each cell stores a pair (length, count), and two pairs merge as follows: keep the larger length with its count; if the lengths are equal, add the counts. That merge is associative and commutative, which is all a Fenwick tree needs for prefix queries and point updates.

For each x = nums[i] with rank r:

  1. Query ranks 1 .. r - 1 (strictly smaller values only, so equal values never chain) to get (len, cnt).
  2. If nothing smaller exists, len = 0 and the chain starts at x with cnt = 1. Either way the chain ending at x has length len + 1.
  3. Merge (len + 1, cnt) into position r, and into the running global best.

Algorithm.

  1. Sort the distinct values to build ranks (coordinate compression).
  2. For each element in array order, do the query and the update described above.
  3. Return the count stored with the best length.
static int optimal(int[] nums) {
    int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
    int m = sorted.length, bestLen = 0, bestCnt = 0;
    int[] treeLen = new int[m + 1], treeCnt = new int[m + 1];
    for (int x : nums) {
        int r = Arrays.binarySearch(sorted, x) + 1;         // 1-based rank of x
        int len = 0, cnt = 0;
        for (int i = r - 1; i > 0; i -= i & -i) {           // best chain ending in a strictly smaller value
            if (treeLen[i] > len) { len = treeLen[i]; cnt = treeCnt[i]; }
            else if (treeLen[i] == len) cnt += treeCnt[i];
        }
        if (len == 0) cnt = 1;                              // x starts a new chain on its own
        len++;
        for (int i = r; i <= m; i += i & -i) {              // record the chain ending at x
            if (len > treeLen[i]) { treeLen[i] = len; treeCnt[i] = cnt; }
            else if (len == treeLen[i]) treeCnt[i] += cnt;
        }
        if (len > bestLen) { bestLen = len; bestCnt = cnt; }
        else if (len == bestLen) bestCnt += cnt;
    }
    return bestCnt;
}

Complexity. Time O(n log n): sorting, plus one O(log n) query and update per element. Space O(n) for the ranks and the two tree arrays.

Edge cases and pitfalls