Advanced Longest Increasing Subsequence

Longest Increasing Subsequence (LIS: LeetCode 300)

Reviewing the two primary solutions for the standard LIS problem.

// O(N^2) Dynamic Programming Solution
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

// O(N log N) Greedy + Binary Search (Patience Sorting)
public int lengthOfLIS_Fast(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    for (int num : nums) {
        int lo = 0, hi = tails.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails.get(mid) < num) lo = mid + 1;
            else hi = mid;
        }
        if (lo == tails.size()) tails.add(num);
        else tails.set(lo, num);
    }
    return tails.size();
}

Russian Doll Envelopes (LeetCode 354)

One envelope can fit into another if both its width and height are smaller.

Strategy: Sort by width in ascending order. If widths are tied, sort heights in descending order. Then, find the LIS of heights.

Why the descending height tie-breaker? If two envelopes have the same width, the LIS calculation among their heights should not count them both (since one cannot contain the other). Sorting the heights descending ensures that in a set of equal-width envelopes, at most one can be included in the increasing subsequence.

public int maxEnvelopes(int[][] envelopes) {
    // Sort: Width ascending, then Height descending
    Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
    
    // Extract heights and compute LIS in O(N log N)
    int n = envelopes.length;
    int[] tails = new int[n];
    int size = 0;
    for (int[] e : envelopes) {
        int h = e[1];
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < h) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = h;
        if (lo == size) size++;
    }
    return size;
}

Number of Longest Increasing Subsequences (LeetCode 673)

Maintain two arrays: dp[i] for the length of LIS ending at $i$, and counts[i] for the number of such LIS.

public int findNumberOfLIS(int[] nums) {
    int n = nums.length;
    if (n <= 1) return n;
    int[] lengths = new int[n]; // length of LIS ending at i
    int[] counts = new int[n];   // count of LIS ending at i
    Arrays.fill(lengths, 1);
    Arrays.fill(counts, 1);
    
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (lengths[j] + 1 > lengths[i]) {
                    lengths[i] = lengths[j] + 1;
                    counts[i] = counts[j];
                } else if (lengths[j] + 1 == lengths[i]) {
                    counts[i] += counts[j];
                }
            }
        }
        maxLen = Math.max(maxLen, lengths[i]);
    }
    
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (lengths[i] == maxLen) result += counts[i];
    }
    return result;
}

Evolution Summary Table