Longest Increasing Subsequence and the DP-on-Subsequences Family

Longest increasing subsequence is the cleanest example of a "DP over prefixes where the state is where the subsequence ends". Once you see that state, a dozen problems that look unrelated, from nesting envelopes to stacking boxes to chaining words, turn into the same twenty lines of code with a different comparison. This guide walks through both standard algorithms with dry runs, proves why the fast one works, and then works through the variants interviewers actually ask, with C++ and Python code you can trust (every snippet here has been run against the LeetCode examples).

If you just want the base problem solved line by line, the dedicated LeetCode 300 walkthrough is shorter. This page is about the family.

What the Longest Increasing Subsequence Problem Actually Asks

Given an array, pick indices i1 < i2 < ... < ik so that nums[i1] < nums[i2] < ... < nums[ik], and maximise k. A subsequence keeps the original order but may skip elements; a subarray must be contiguous. Candidates who blur these two lose ten minutes writing a sliding window that cannot work.

For nums = [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4, achieved by [2, 3, 7, 18], [2, 5, 7, 101] and a few others. Notice that the answer is not unique, which matters later when a problem asks you to count the longest subsequences or return one of them.

Why brute force fails: there are 2ⁿ subsequences. At n = 2,500 (LeetCode 300's limit) that is hopeless, so we need to reuse work. The reusable unit is "the best increasing subsequence that ends exactly here".

The O(n²) DP: State, Transition and Dry Run

State: dp[i] is the length of the longest strictly increasing subsequence whose last element is nums[i]. Pinning the last element is the whole trick: to append nums[i] to an earlier subsequence you only need to know that subsequence's last value, and that is exactly what the index encodes.

Transition: dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), or 1 if no such j exists. Answer: max(dp), not dp[n-1], because the LIS can end anywhere.

int lisQuadratic(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

def lis_n2(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)

Dry run on [10, 9, 2, 5, 3, 7, 101, 18]

max(dp) = 4. Time is O(n²) because of the double loop; space is O(n). For n up to about 5,000 this is comfortably fast in C++ and fine in Python up to roughly 2,500. The quadratic version is worth knowing well even though a faster one exists, because almost every variant below (counting, divisibility, string chains) only works with the explicit dp[j] loop.

The O(n log n) LIS Algorithm (Patience Sorting) and Why It Works

The quadratic DP asks, for each element, "what is the best subsequence I can extend?" The fast version flips the question: for each length L, what is the smallest value that can end an increasing subsequence of length L? Call it tails[L-1]. A smaller tail is always at least as good as a larger one, because anything that can extend the larger tail can also extend the smaller one.

Two facts make it work:

1. tails is strictly increasing. If a length-L subsequence ends at value v, dropping its last element gives a length-(L-1) subsequence ending at something smaller than v. So the best tail for L-1 is less than the best tail for L.
2. Each new x changes exactly one entry. Find the first tail that is >= x (that is lower_bound). If none exists, x extends the longest subsequence, so append. Otherwise x can replace that tail: it extends the subsequence of length k (whose tail is < x) into a length k+1 one with a smaller ending.

Because tails is sorted, finding the position is a binary search, giving O(n log n) total. The final length of tails is the LIS length.

int lengthOfLIS(const vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

from bisect import bisect_left

def lis_nlogn(nums):
    tails = []
    for x in nums:
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails)

Dry run of the tails array

Length 4. Here the final tails happens to be a valid LIS, but that is luck. Try [3, 4, 5, 1]: tails ends as [1, 4, 5], which is not a subsequence at all since 1 comes after 5. Interviewers love asking "is tails the answer?" precisely to catch this.

Strict vs non-decreasing, increasing vs decreasing

Why upper_bound for non-decreasing: when x equals an existing tail, you want x to extend that subsequence (equal values are allowed), so you must skip past equal tails and replace the first strictly greater one.

How to Print the Actual Longest Increasing Subsequence

Many interviewers follow up with "now return the subsequence itself". In the O(n²) version this is easy: store parent[i] = j whenever dp[j] + 1 improves dp[i], then walk back from the index with the largest dp.

In the O(n log n) version, store indices instead of values in tails. When element i lands at position k, its predecessor is whatever index sits at tails[k-1] at that moment. That predecessor ended a valid length-k subsequence before i, so the chain of parents is always a real subsequence even though tails itself is not.

vector<int> lisSequence(const vector<int>& nums) {
    int n = nums.size();
    vector<int> tailIdx;          // tailIdx[k] = index of best tail for length k+1
    vector<int> parent(n, -1);
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = tailIdx.size();
        while (lo < hi) {             // first position whose tail >= nums[i]
            int mid = (lo + hi) / 2;
            if (nums[tailIdx[mid]] < nums[i]) lo = mid + 1;
            else hi = mid;
        }
        if (lo > 0) parent[i] = tailIdx[lo - 1];
        if (lo == (int)tailIdx.size()) tailIdx.push_back(i);
        else tailIdx[lo] = i;
    }
    vector<int> seq;
    for (int i = tailIdx.empty() ? -1 : tailIdx.back(); i != -1; i = parent[i])
        seq.push_back(nums[i]);
    reverse(seq.begin(), seq.end());
    return seq;
}

On the running example this returns [2, 3, 7, 18]. On [3, 4, 5, 1] it returns [3, 4, 5], correctly ignoring the 1 that sits in tails. The cost is still O(n log n) time and O(n) extra space.

Number of Longest Increasing Subsequences (LeetCode 673)

Now count how many distinct index-sequences achieve the maximum length. The fix is to carry a second array: cnt[i] = number of LIS-ending-at-i of length len[i]. When you scan j:

• If len[j] + 1 > len[i]: you found a strictly longer way. Set len[i] = len[j] + 1 and reset cnt[i] = cnt[j].
• If len[j] + 1 == len[i]: another way to reach the same best length. Add cnt[i] += cnt[j].

The answer sums cnt[i] over all i whose len[i] equals the global maximum.

int findNumberOfLIS(const vector<int>& nums) {
    int n = nums.size();
    vector<int> len(n, 1), cnt(n, 1);
    int best = 0, total = 0;
    for (int i = 0; i < n; i++) {
        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]; }
            else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
        }
        if (len[i] > best) { best = len[i]; total = cnt[i]; }
        else if (len[i] == best) total += cnt[i];
    }
    return total;
}

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)

Dry run on [1, 3, 5, 4, 7]: len becomes [1, 2, 3, 3, 4] and cnt becomes [1, 1, 1, 1, 2]. At index 4 (value 7), both 5 (len 3) and 4 (len 3) give length 4, so the counts add to 2: the sequences [1,3,5,7] and [1,3,4,7]. For [2, 2, 2, 2, 2] every len is 1 and every cnt is 1, so the answer is 5, one per element.

The classic bug is writing cnt[i] += cnt[j] in the first branch too, which keeps stale counts from shorter lengths. If the interviewer pushes for O(n log n), the standard answer is a Fenwick tree or segment tree indexed by compressed value, storing (maxLen, ways) and merging by "larger length wins, equal lengths add counts". Querying all values below nums[i] gives the best predecessor in O(log n). See the segment tree and Fenwick tree guide for the structure itself.

Russian Doll Envelopes (LeetCode 354): LIS in Two Dimensions

Envelope (w1, h1) fits inside (w2, h2) only if w1 < w2 and h1 < h2. Find the longest nesting chain. With up to 10⁵ envelopes, O(n²) times out, so we need a reduction to the fast LIS.

Step 1: sort by width so that any valid chain appears left to right. Step 2: run LIS on heights. The trap is equal widths: (3,4) and (3,5) cannot nest, yet an LIS on heights 4, 5 would chain them. The fix is to sort equal widths by height descending. Then among envelopes of the same width the heights decrease, so a strictly increasing subsequence can pick at most one of them.

int maxEnvelopes(vector<vector<int>>& env) {
    sort(env.begin(), env.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
    });
    vector<int> tails;
    for (auto& e : env) {
        auto it = lower_bound(tails.begin(), tails.end(), e[1]);
        if (it == tails.end()) tails.push_back(e[1]);
        else *it = e[1];
    }
    return tails.size();
}

from bisect import bisect_left

def max_envelopes(envelopes):
    envelopes.sort(key=lambda e: (e[0], -e[1]))
    tails = []
    for _, h in envelopes:
        k = bisect_left(tails, h)
        if k == len(tails):
            tails.append(h)
        else:
            tails[k] = h
    return len(tails)

Dry run: [[5,4],[6,4],[6,7],[2,3]] sorts to [2,3], [5,4], [6,7], [6,4]. Heights: 3, 4, 7, 4. Tails: [3], [3,4], [3,4,7], then 4 replaces 4 at position 1, so [3,4,7]. Answer 3: [2,3] → [5,4] → [6,7]. Had we sorted [6,4] before [6,7], heights would be 3, 4, 4, 7 and still give 3 here, but on input like [[1,1],[1,2],[1,3]] ascending heights would wrongly return 3 instead of 1.

The same trick handles "maximum number of people in a circus tower" (height and weight) and any "both dimensions strictly larger" chain. When the problem allows rotating items, as in box stacking, you generate all orientations first and fall back to the O(n²) DP, because sorting alone no longer gives a valid order on all three dimensions.

Chain Problems: Pair Chain, String Chain, Divisible Subset

"Chain" problems ask for the longest sequence where each element can follow the previous one. The recipe is always: find a sort order in which every valid chain appears left to right, then run the LIS-shaped DP with a custom "can follow" check. Sometimes a greedy beats the DP; knowing when is the interview signal.

Maximum Length of Pair Chain (LeetCode 646)

Pair (c, d) can follow (a, b) if b < c. You can pick pairs in any order. Sorting by start and running O(n²) LIS works, but this is really interval scheduling: sort by end and greedily take every pair whose start is after the last chosen end. Picking the earliest-finishing pair never hurts, because it leaves the most room for the rest. O(n log n) for the sort, O(1) extra.

def find_longest_chain(pairs):
    pairs.sort(key=lambda p: p[1])
    count, cur_end = 0, float('-inf')
    for a, b in pairs:
        if a > cur_end:
            count += 1
            cur_end = b
    return count

If an interviewer asks why greedy works here but not for Russian dolls: pairs only constrain one boundary (end before start), which is the exchange-argument setting of classic greedy problems. Envelopes constrain two independent dimensions, so no single sort key makes a local choice safe.

Longest String Chain (LeetCode 1048)

Word B is a successor of A if you can insert exactly one letter into A to get B. Sort words by length (a predecessor is always one shorter), then for each word try deleting each character and look up the result in a hash map of best chain lengths. With n words of length up to L, time is O(n log n + n · L²): L deletions, each building a string of length L.

def longest_str_chain(words):
    words.sort(key=len)
    best = {}
    ans = 1
    for w in words:
        best[w] = 1
        for i in range(len(w)):
            prev = w[:i] + w[i + 1:]
            if prev in best:
                best[w] = max(best[w], best[prev] + 1)
        ans = max(ans, best[w])
    return ans

This is LIS with the inner loop replaced by a hash lookup: instead of scanning all earlier j, you generate the only L candidates that could be predecessors. That inversion, "enumerate predecessors instead of scanning", is worth naming in the interview.

Largest Divisible Subset (LeetCode 368)

Return the largest subset where every pair divides one way or the other. After sorting, divisibility is transitive along the chain: if a | b and b | c then a | c. So a valid subset is just a chain where each element divides the next, and you run the O(n²) LIS with nums[i] % nums[j] == 0 as the comparison, plus a parent array to return the subset.

vector<int> largestDivisibleSubset(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size(), best = 0;
    vector<int> dp(n, 1), parent(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        if (dp[i] > dp[best]) best = i;
    }
    vector<int> out;
    for (int i = best; i != -1; i = parent[i]) out.push_back(nums[i]);
    reverse(out.begin(), out.end());
    return out;
}

For [1, 2, 4, 8] it returns the whole array; for [1, 2, 3] it returns [1, 2]. No binary search speed-up exists here because divisibility is not a total order, which is a nice point to make if asked about O(n log n).

LIS in Disguise: Mountains, Deletions, K-Increasing and LCS

Minimum deletions to make an array sorted

The elements you keep must form a non-decreasing subsequence, so keep the longest one: answer = n - (longest non-decreasing subsequence). Same idea for "minimum moves to sort a permutation by moving elements anywhere": the untouched elements form an increasing subsequence.

Minimum Removals to Make a Mountain Array (LeetCode 1671)

A mountain strictly rises then strictly falls. Compute left[i] = LIS ending at i from the left and right[i] = LIS ending at i from the right (that is, longest decreasing sequence starting at i). For each peak with left[i] > 1 and right[i] > 1 (a mountain needs both slopes), the mountain length is left[i] + right[i] - 1. Answer = n - max. For [2,1,1,5,6,2,3,1] the best mountain is [1,5,6,3,1] of length 5, so 3 removals. The same pair of arrays solves the longest bitonic subsequence directly.

Minimum Operations to Make the Array K-Increasing (LeetCode 2111)

The condition arr[i-k] <= arr[i] only links indices in the same residue class mod k. Split the array into k independent subsequences, and for each one keep its longest non-decreasing subsequence (note the bisect_right). Operations = total length minus the sum of those LIS lengths. With n up to 10⁵, the O(n log n) version is required.

from bisect import bisect_right

def k_increasing(arr, k):
    ops = 0
    for start in range(k):
        tails, cnt = [], 0
        for i in range(start, len(arr), k):
            cnt += 1
            pos = bisect_right(tails, arr[i])
            if pos == len(tails):
                tails.append(arr[i])
            else:
                tails[pos] = arr[i]
        ops += cnt - len(tails)
    return ops

LCS of two sequences when one has distinct values

General longest common subsequence is O(n·m), covered in the DP on strings guide. But if target has distinct values, map each value to its index in target, drop elements of the other array not in target, and the LCS becomes the LIS of the mapped indices. That is exactly LeetCode 1713 (Minimum Operations to Make a Subsequence), where n = 10⁵ makes the O(n log n) reduction mandatory. This reduction is a favourite "hard" follow-up because it connects two DP families.

Quick reference: which version do I need?

How LIS Shows Up in Coding Interviews

LIS is popular because it has a natural ladder of follow-ups, letting one interviewer separate several levels of candidates in 45 minutes. A typical progression in product-company rounds:

1. Base length. Can you define a DP state and get O(n²) working cleanly? Most candidates pass this.
2. Optimise. "n is 10⁵." You need the tails idea, and the interviewer will ask you to justify replacing an element. The two-fact argument above (tails is sorted, smaller tails dominate) is the answer they want.
3. Return the sequence. Tests whether you know tails is not the sequence. Parent pointers on indices.
4. Twist the comparison. Non-decreasing, two dimensions, divisibility. Tests whether you understand the template or memorised it.
5. Count. Number of LIS checks careful state updates under pressure.

Things that earn points: stating that the answer is max(dp) and not dp[n-1], naming the equal-width trap in envelopes before the interviewer does, testing on a case with duplicates like [2, 2, 2] (strict LIS is 1), and mentioning when greedy suffices. If you narrate these checks while coding, it reads as real understanding; the guide on thinking out loud in coding interviews covers how to do that without slowing down.

Common LIS Mistakes

• Returning dp[n-1]. The LIS rarely ends at the last element. Use max(dp).
• Wrong bound function. upper_bound on a strictly-increasing problem lets duplicates count; [2,2,2] would return 3. Always test with duplicates.
• Presenting tails as the subsequence. Use [3,4,5,1] as your mental counter-example.
• Envelopes sorted height ascending on ties. Breaks on equal widths.
• Number of LIS: adding when you should reset. A longer length must overwrite the count, not add to it.
• Forgetting to sort in chain problems. String chain without sorting by length can process a word before its predecessor and miss chains.
• Integer overflow on counts. LeetCode 673 fits in a 32-bit int by its constraints, but in general the number of LIS can grow exponentially; use long long or take a modulus if the problem specifies one.

Practice Order for LIS and DP on Subsequences

Solve in this order; each problem adds exactly one new idea on top of the previous one:

1. LeetCode 674 Longest Continuous Increasing Subsequence (the subarray warm-up, to feel the difference).
2. LeetCode 300 Longest Increasing Subsequence: write both versions from memory.
3. LeetCode 646 Maximum Length of Pair Chain: try DP, then greedy.
4. LeetCode 368 Largest Divisible Subset: parent pointers.
5. LeetCode 673 Number of LIS: the count array.
6. LeetCode 1048 Longest String Chain: enumerate predecessors.
7. LeetCode 354 Russian Doll Envelopes: the tie-breaking sort.
8. LeetCode 1671 Minimum Removals to Make Mountain Array: LIS from both sides.
9. LeetCode 2111 K-Increasing: non-decreasing LIS per residue class.
10. LeetCode 1713 Minimum Operations to Make a Subsequence: LCS to LIS reduction.

After these, revisit them a week later and only write the state definition and sort order for each. If you can do that in under a minute per problem, the pattern is locked in. For the wider picture of how LIS fits next to knapsack, interval and grid DP, see the knapsack patterns guide and the DP interview questions roundup.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.