AlgoInsight

Free lesson · DSA Mastery - Interview Prep, End to End

Longest Increasing Subsequence

Hard5 min readdsadynamic-programming

Introduction to Longest Increasing Subsequence

Longest Increasing Subsequence (LIS) turns the page from selection under a budget - the knapsack family - to ordering and chaining: finding the longest subsequence whose elements satisfy a "can-follow" relation, classically "strictly increasing values." You already glimpsed this in Maximum Length of Pair Chain, whose dp[i] = longest chain ending at i is the LIS skeleton with a compatibility test. This introductory topic develops that skeleton fully - the O(n²) "extend any compatible predecessor" DP and the O(n log n) patience-sorting refinement - so the four problems that follow are recognized as the same pattern applied to richer relations.

A subsequence is formed by deleting zero or more elements without reordering the rest. So [3, 9, 5, 7] has [3, 5, 7] as an increasing subsequence (delete the 9), but not [9, 5] (not increasing) or [3, 7, 5] (out of order). LIS asks for the length of the longest such increasing subsequence. The subtlety that makes it interesting: a greedy "always extend if larger" fails, because the best subsequence may skip a large early element to keep smaller options open later.

Important: The LIS state is dp[i] = the length of the longest increasing subsequence ending at index i (i.e., with nums[i] as its last element). This "ending at i" framing - not "using the first i elements" - is what makes the transition clean: a subsequence ending at i extends some shorter subsequence ending at an earlier compatible index. The global answer is the maximum dp[i] over all i.

The Core Idea: Extend Compatible Predecessors

Fix index i. Any increasing subsequence ending at nums[i] has, just before nums[i], some earlier element nums[j] (with j < i) that is smaller than nums[i] - otherwise nums[i] could not follow it while staying increasing. So a subsequence ending at i is formed by taking some subsequence ending at a compatible j and appending nums[i]. To make it as long as possible, pick the j whose dp[j] is largest among all compatible predecessors:

dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i].

If no smaller earlier element exists, nums[i] starts a fresh subsequence of length 1. The 1 + accounts for nums[i] itself; the max(dp[j]) finds the best subsequence to extend.

Note: This is exactly the structure of Maximum Length of Pair Chain - dp[i] = longest chain ending at i, extending any earlier compatible pair. The only thing that changes between LIS-family problems is the compatibility test: "value strictly greater" for plain LIS, "pair ends before this starts" for pair chains, "string is a predecessor by one inserted letter" for string chains, "fixed common difference" for arithmetic subsequences. The skeleton - dp[i] = longest ending at i, extend compatible predecessors - is invariant.

The O(n²) DP

The direct implementation tries, for each i, every earlier j, giving O(n²).

// O(n^2) LIS: dp[i] = longest increasing subsequence ending at index i.
public static int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    java.util.Arrays.fill(dp, 1);                       // each element alone is a subsequence of length 1
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i])                       // compatible predecessor (strictly smaller)
                dp[i] = Math.max(dp[i], dp[j] + 1);      // extend the best subsequence ending at j
        }
        best = Math.max(best, dp[i]);                    // LIS can end anywhere
    }
    return best;
}

This Java code computes the longest increasing subsequence in quadratic time: each element's best length extends the longest compatible earlier subsequence, and the answer is the maximum over all ending positions.

The O(n log n) Refinement: Patience Sorting

A faster approach maintains an array tails, where tails[k] = the smallest possible tail value of any increasing subsequence of length k+1 seen so far. For each new value, binary-search for the first tail >= it and replace that tail (or append, if the value exceeds all tails). The length of tails at the end is the LIS length. This is the "patience sorting" idea: greedily keep each achievable length's tail as small as possible to maximize future extensibility.

// O(n log n) LIS via patience sorting: tails[k] = smallest tail of an increasing subseq of length k+1.
public static int lengthOfLISFast(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;                                        // current number of distinct lengths
    for (int x : nums) {
        int lo = 0, hi = size;
        while (lo < hi) {                                // binary search: first tail >= x
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < x) lo = mid + 1; else hi = mid;
        }
        tails[lo] = x;                                   // replace (keep tails minimal) or extend
        if (lo == size) size++;                          // x extended the longest run
    }
    return size;                                          // LIS length
}

This Java code computes the longest increasing subsequence in n-log-n time using patience sorting: it keeps the smallest possible tail for each subsequence length and binary-searches to place each value, returning the number of distinct lengths.

Warning: The tails array is not itself a valid LIS - its values may come from different positions and not form an actual subsequence. Only its length is meaningful (it equals the LIS length). Reconstructing an actual LIS requires extra bookkeeping (parent pointers). Do not mistake tails for the answer subsequence.

How the Four Problems Map to This Pattern

Note:

  • Number of LIS - count how many longest increasing subsequences exist (augment the DP with a count alongside the length).
  • Longest String Chain - chain words where each is formed by inserting one letter into the predecessor (compatibility = "predecessor by one insertion"; sort by length).
  • Longest Arithmetic Subsequence - longest subsequence with a constant difference (state augmented by the common difference).
  • Russian Doll Envelopes - nest 2-D envelopes (reduce to 1-D LIS via a clever two-key sort).

Each is the LIS skeleton with a different compatibility relation or an augmented state.

Why This Topic Matters

LIS establishes the dp[i] = longest increasing subsequence ending at index i state and the transition dp[i] = 1 + max(dp[j]) over compatible earlier predecessors (nums[j] < nums[i]), with the global answer being the max over all i. The O(n²) DP extends every compatible predecessor; the O(n log n) patience-sorting refinement keeps the smallest tail per length and binary-searches each value. The deep insight - reused throughout this sub-group - is that LIS is not about "increasing" specifically but about the longest sequence under any can-follow relation: swap the compatibility test (or augment the state) and the same skeleton solves pair chains, string chains, arithmetic subsequences, and 2-D nesting.

The next topic, Number of LIS, augments the LIS DP to count the longest increasing subsequences rather than just measure their length: given an array, return how many distinct increasing subsequences achieve the maximum length. The key idea is to carry two arrays - length[i] (the LIS length ending at i, as before) and count[i] (how many such longest subsequences end at i) - and update them together: when extending predecessor j strictly improves the length at i, the count resets to count[j]; when it ties the current best length at i, the count accumulates (count[i] += count[j]). It shows how to enrich an optimization DP with a companion counting DP, a broadly useful technique for "how many optimal solutions are there?" questions that recurs whenever you must count the ways an optimum is achieved.

Back to DSA Mastery - Interview Prep, End to End