Longest Increasing Subsequence (LIS) Family

1. Introduction and Motivation

The Longest Increasing Subsequence (LIS) problem asks: given an array of numbers, what is the length of the longest subsequence whose elements are strictly increasing? A subsequence keeps the relative order of the original array but need not be contiguous — elements can be skipped. LIS shows up directly in patience-sorting card games, box-stacking and scheduling problems, and as the core subroutine inside 2D geometry problems like Russian Doll Envelopes.

This lesson assumes you are already comfortable with the general DP methodology — turning a brute-force recursion into a defined state, a recurrence, and a base case — built in Part 14: Dynamic Programming Foundations and applied across recognizable shapes in Part 15: Core DP Patterns. Neither of those is re-derived here; if the phrase "define dp[i], then find its recurrence" feels unfamiliar, read those two first.

What makes the LIS family worth its own lesson is that the "obvious" $O(n^2)$ DP is only the beginning. An $O(n \log n)$ reformulation exists, but it is built on a subtler invariant that does not directly hand you the answer's elements — recovering the actual subsequence, or counting how many optimal subsequences exist, requires extra bookkeeping layered on top of whichever base algorithm you choose.

2. A Concrete Example

Worked Example

Finding the LIS of [10, 9, 2, 5, 3, 7, 101, 18]

Scan left to right and, for each index, ask: "what is the longest increasing run that could end here, using only elements already seen?" Track that as dp[i].

Index	Value	Smaller earlier values	dp[i]
0	10	none	1
1	9	none (10 is not smaller)	1
2	2	none	1
3	5	2 (dp=1)	2
4	3	2 (dp=1)	2
5	7	2, 5, 3 — best is 5 (dp=2)	3
6	101	everything before it — best is 7 (dp=3)	4
7	18	all but 101 — best is 7 (dp=3)	4

The largest dp value is 4, so the LIS length is 4. Two possible subsequences achieve it: [2, 5, 7, 101] and [2, 3, 7, 101] (also [2, 5, 7, 18] and [2, 3, 7, 18]).

3. O(n²) DP Approach

                Core insight: Define $dp[i]$ = the length of the longest increasing subsequence that ends exactly at index $i$ (not just anywhere in $0..i$). Then $dp[i] = 1 + \max(dp[j])$ over every $j < i$ with $arr[j] < arr[i]$, and $dp[i] = 1$ when no such $j$ exists. The answer to the whole problem is $\max_i dp[i]$, not $dp[n-1]$ — the longest run does not have to end at the last element.
            

This is a direct translation of the trace above: for every index $i$, look back at every earlier index $j$, and if $arr[j] < arr[i]$, index $i$ could extend whatever increasing run ends at $j$. Trying every earlier index gives $O(n)$ work per index and $O(n^2)$ overall.

def lis_length(nums):
    """
    O(n^2) DP: dp[i] = length of the longest increasing
    subsequence that ends exactly at index i.
    Time: O(n^2), Space: O(n)
    """
    if not nums:
        return 0, []
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp), dp

# Example
sample = [10, 9, 2, 5, 3, 7, 101, 18]
length, dp = lis_length(sample)
print("Array:", sample)
print("dp:", dp)              # [1, 1, 1, 2, 2, 3, 4, 4]
print("LIS length:", length)  # 4

#include <iostream>
#include <vector>
#include <algorithm>

// O(n^2) DP: dp[i] = length of the longest increasing
// subsequence that ends exactly at index i.
int lisLength(const std::vector<int>& nums, std::vector<int>& dp) {
    int n = nums.size();
    if (n == 0) return 0;
    dp.assign(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> sample{10, 9, 2, 5, 3, 7, 101, 18};
    std::vector<int> dp;
    int length = lisLength(sample, dp);

    std::cout << "dp:";
    for (int v : dp) std::cout << ' ' << v;
    std::cout << '\n';
    std::cout << "LIS length: " << length << '\n'; // 4
}

import java.util.Arrays;

public class LongestIncreasingSubsequence {
    // O(n^2) DP: dp[i] = length of the longest increasing
    // subsequence that ends exactly at index i.
    static int lisLength(int[] nums, int[] dp) {
        int n = nums.length;
        if (n == 0) return 0;
        Arrays.fill(dp, 1);
        int best = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] sample = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] dp = new int[sample.length];
        int length = lisLength(sample, dp);

        System.out.println("dp: " + Arrays.toString(dp));
        System.out.println("LIS length: " + length); // 4
    }
}

4. O(n log n) Patience Sorting Method

                Core insight: Maintain an array tails where $tails[k]$ is the smallest possible tail value among all increasing subsequences of length $k+1$ discovered so far. For each new element, binary-search tails for the leftmost position whose value is $\geq$ the new element and overwrite it there; if the new element is larger than every value in tails, append it. The final length of tails is the LIS length.
            

The name comes from the solitaire card game Patience: you deal cards one at a time, placing each on the leftmost pile whose top card is greater than or equal to it, or starting a new pile to its right if no such pile exists. The number of piles at the end equals the longest increasing run you could have drawn out.

Why tails is not itself a subsequence of the input: its values get overwritten as better (smaller) options appear. In the trace below, tails[0] starts as 10, is overwritten to 9, then to 2 — but 2 never appeared before 9 in the array, so [2, 9] was never a real prefix of anything. tails is an auxiliary structure that always tells you the best possible tail for each achievable length; it is not, and does not need to be, a subsequence you could point to in the original array. That is exactly why recovering the actual elements needs a different technique (covered next).

Read value	Binary search result	tails after
10	append (tails empty)	[10]
9	replace index 0 (10 ≥ 9)	[9]
2	replace index 0 (9 ≥ 2)	[2]
5	append (5 > every tail)	[2, 5]
3	replace index 1 (5 ≥ 3)	[2, 3]
7	append (7 > every tail)	[2, 3, 7]
101	append (101 > every tail)	[2, 3, 7, 101]
18	replace index 3 (101 ≥ 18)	[2, 3, 7, 18]

The final length is 4, matching the DP trace. Notice the binary search is a lower_bound: it finds the leftmost index whose tail is not strictly less than the new value. Getting the comparison direction wrong (using $\leq$ instead of $<$ inside the search, or vice versa) silently breaks the "smallest possible tail" invariant, so trace the bounds carefully when adapting this to a non-strict ("non-decreasing") variant.

def lis_length_fast(nums):
    """
    O(n log n) patience sorting.
    tails[k] = smallest possible tail value of any increasing
    subsequence of length k + 1 found so far. tails is NOT
    itself a valid subsequence of nums -- see the article text.
    """
    tails = []
    for num in nums:
        lo, hi = 0, len(tails)
        # lower_bound: leftmost position whose tail is >= num
        while lo < hi:
            mid = (lo + hi) // 2
            if tails[mid] < num:
                lo = mid + 1
            else:
                hi = mid
        if lo == len(tails):
            tails.append(num)
        else:
            tails[lo] = num
    return len(tails), tails

# Example
sample = [10, 9, 2, 5, 3, 7, 101, 18]
length, tails = lis_length_fast(sample)
print("Array:", sample)
print("Final tails:", tails)  # [2, 3, 7, 18]
print("LIS length:", length)  # 4

#include <iostream>
#include <vector>

// O(n log n) patience sorting.
int lisLengthFast(const std::vector<int>& nums, std::vector<int>& tails) {
    tails.clear();
    for (int num : nums) {
        int lo = 0, hi = tails.size();
        // lower_bound: leftmost position whose tail is >= num
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < num) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        if (lo == (int)tails.size()) {
            tails.push_back(num);
        } else {
            tails[lo] = num;
        }
    }
    return tails.size();
}

int main() {
    std::vector<int> sample{10, 9, 2, 5, 3, 7, 101, 18};
    std::vector<int> tails;
    int length = lisLengthFast(sample, tails);

    std::cout << "Final tails:";
    for (int v : tails) std::cout << ' ' << v;
    std::cout << '\n';
    std::cout << "LIS length: " << length << '\n'; // 4
}

import java.util.ArrayList;
import java.util.List;

public class LisPatienceSorting {
    // O(n log n) patience sorting.
    static int lisLengthFast(int[] nums, List<Integer> tails) {
        tails.clear();
        for (int num : nums) {
            int lo = 0, hi = tails.size();
            // lower_bound: leftmost position whose tail is >= num
            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();
    }

    public static void main(String[] args) {
        int[] sample = {10, 9, 2, 5, 3, 7, 101, 18};
        List<Integer> tails = new ArrayList<>();
        int length = lisLengthFast(sample, tails);

        System.out.println("Final tails: " + tails);
        System.out.println("LIS length: " + length); // 4
    }
}

5. Reconstructing the Actual LIS

                Core insight: Neither algorithm above hands you the actual elements — the $O(n^2)$ version only tracks lengths, and the tails array is explicitly not a real subsequence. To recover the elements, track a parent[i] pointer alongside $dp[i]$ during the $O(n^2)$ pass: whenever extending from index $j$ improves $dp[i]$, record parent[i] = j. After the pass, find the index with the largest $dp$ value and walk its parent chain backward.
            

The $O(n^2)$ version is the natural base for this because parent[i] is a direct byproduct of the same comparison that already updates dp[i] — no extra structure is needed. (Patience sorting can also be extended to support reconstruction, but it requires a second parent array threaded through the binary-search step, which is more error-prone to get right.)

def lis_reconstruct(nums):
    """
    O(n^2) DP with parent pointers to recover the actual
    longest increasing subsequence, not just its length.
    """
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n
    parent = [-1] * n
    best_idx = 0
    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
                parent[i] = j
        if dp[i] > dp[best_idx]:
            best_idx = i

    sequence = []
    idx = best_idx
    while idx != -1:
        sequence.append(nums[idx])
        idx = parent[idx]
    sequence.reverse()
    return sequence

# Example
sample = [10, 9, 2, 5, 3, 7, 101, 18]
print("Array:", sample)
print("Actual LIS:", lis_reconstruct(sample))  # [2, 5, 7, 101]

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> lisReconstruct(const std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {};
    std::vector<int> dp(n, 1), parent(n, -1);
    int bestIdx = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > dp[bestIdx]) bestIdx = i;
    }

    std::vector<int> sequence;
    for (int idx = bestIdx; idx != -1; idx = parent[idx]) {
        sequence.push_back(nums[idx]);
    }
    std::reverse(sequence.begin(), sequence.end());
    return sequence;
}

int main() {
    std::vector<int> sample{10, 9, 2, 5, 3, 7, 101, 18};
    std::vector<int> lis = lisReconstruct(sample);

    std::cout << "Actual LIS:";
    for (int v : lis) std::cout << ' ' << v;
    std::cout << '\n'; // 2 5 7 101
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LisReconstruct {
    static List<Integer> lisReconstruct(int[] nums) {
        int n = nums.length;
        List<Integer> sequence = new ArrayList<>();
        if (n == 0) return sequence;

        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        int bestIdx = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            if (dp[i] > dp[bestIdx]) bestIdx = i;
        }

        for (int idx = bestIdx; idx != -1; idx = parent[idx]) {
            sequence.add(nums[idx]);
        }
        Collections.reverse(sequence);
        return sequence;
    }

    public static void main(String[] args) {
        int[] sample = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Actual LIS: " + lisReconstruct(sample)); // [2, 5, 7, 101]
    }
}

Counting the Number of LIS

A related but different question: how many distinct subsequences achieve the maximum length? Keep a parallel count[i] array alongside $dp[i]$. When extending from $j$ strictly improves $dp[i]$ (a new best length), the count resets to count[j]. When extending from $j$ merely ties the current best length, add count[j] onto the running total — that earlier subsequence contributes its own set of optimal ways to reach $i$.

def count_lis(nums):
    """
    Parallel count[i] array: number of distinct longest
    increasing subsequences that end exactly at index i.
    """
    if not nums:
        return 0, 0
    n = len(nums)
    dp = [1] * n
    count = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    count[i] = count[j]
                elif dp[j] + 1 == dp[i]:
                    count[i] += count[j]

    longest = max(dp)
    total = sum(c for d, c in zip(dp, count) if d == longest)
    return longest, total

# Example
sample = [10, 9, 2, 5, 3, 7, 101, 18]
length, total = count_lis(sample)
print("Array:", sample)
print("LIS length:", length)             # 4
print("Number of distinct LIS:", total)  # 4

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

std::pair<int,int> countLis(const std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {0, 0};
    std::vector<int> dp(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 (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    count[i] = count[j];
                } else if (dp[j] + 1 == dp[i]) {
                    count[i] += count[j];
                }
            }
        }
    }
    int longest = *std::max_element(dp.begin(), dp.end());
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] == longest) total += count[i];
    }
    return {longest, total};
}

int main() {
    std::vector<int> sample{10, 9, 2, 5, 3, 7, 101, 18};
    std::pair<int,int> result = countLis(sample);
    std::cout << "LIS length: " << result.first << '\n';             // 4
    std::cout << "Number of distinct LIS: " << result.second << '\n'; // 4
}

import java.util.Arrays;

public class CountLis {
    static int[] countLis(int[] nums) {
        int n = nums.length;
        if (n == 0) return new int[]{0, 0};
        int[] dp = new int[n];
        int[] count = new int[n];
        Arrays.fill(dp, 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 (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }

        int longest = 0;
        for (int d : dp) longest = Math.max(longest, d);
        int total = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == longest) total += count[i];
        }
        return new int[]{longest, total};
    }

    public static void main(String[] args) {
        int[] sample = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] result = countLis(sample);
        System.out.println("LIS length: " + result[0]);            // 4
        System.out.println("Number of distinct LIS: " + result[1]); // 4
    }
}

Variants: Decreasing, Bitonic, and Maximum-Sum Increasing Subsequences

Longest Decreasing Subsequence: flip the comparison in the same $O(n^2)$ recurrence — use $arr[j] > arr[i]$ instead of $arr[j] < arr[i]$ — and everything else is identical, so it is not re-derived here.

Longest Bitonic Subsequence (LBS): a bitonic subsequence increases and then decreases (either half may be empty). The trick is to combine two DP passes that you already know how to write: $inc[i]$ = the LIS ending at index $i$ (left-to-right, exactly the recurrence from earlier), and $dec[i]$ = the longest strictly decreasing subsequence starting at index $i$ (computed by scanning right-to-left with the mirrored recurrence). For each index $i$ treated as the peak, the best bitonic length through it is $inc[i] + dec[i] - 1$. The $-1$ matters: $arr[i]$ is counted once inside $inc[i]$ and once again inside $dec[i]$, so without subtracting the shared peak you would double-count it. The answer is $\max_i (inc[i] + dec[i] - 1)$.

def longest_bitonic_subsequence(nums):
    """
    inc[i] = LIS ending at index i (left to right)
    dec[i] = longest strictly decreasing subsequence starting
             at index i (right to left)
    Combine: inc[i] + dec[i] - 1, subtracting 1 because nums[i]
    is counted once in inc[i] and once again in dec[i].
    """
    n = len(nums)
    if n == 0:
        return 0

    inc = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                inc[i] = max(inc[i], inc[j] + 1)

    dec = [1] * n
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if nums[j] < nums[i]:
                dec[i] = max(dec[i], dec[j] + 1)

    return max(inc[i] + dec[i] - 1 for i in range(n))

# Example
sample = [1, 11, 2, 10, 4, 5, 2, 1]
print("Array:", sample)
print("Longest bitonic subsequence length:",
      longest_bitonic_subsequence(sample))  # 6

#include <iostream>
#include <vector>
#include <algorithm>

int longestBitonicSubsequence(const std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    std::vector<int> inc(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                inc[i] = std::max(inc[i], inc[j] + 1);
            }
        }
    }

    std::vector<int> dec(n, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[i]) {
                dec[i] = std::max(dec[i], dec[j] + 1);
            }
        }
    }

    int best = 0;
    for (int i = 0; i < n; i++) {
        best = std::max(best, inc[i] + dec[i] - 1);
    }
    return best;
}

int main() {
    std::vector<int> sample{1, 11, 2, 10, 4, 5, 2, 1};
    std::cout << "Longest bitonic subsequence length: "
              << longestBitonicSubsequence(sample) << '\n'; // 6
}

import java.util.Arrays;

public class LongestBitonicSubsequence {
    static int longestBitonicSubsequence(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        int[] inc = new int[n];
        Arrays.fill(inc, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    inc[i] = Math.max(inc[i], inc[j] + 1);
                }
            }
        }

        int[] dec = new int[n];
        Arrays.fill(dec, 1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[i]) {
                    dec[i] = Math.max(dec[i], dec[j] + 1);
                }
            }
        }

        int best = 0;
        for (int i = 0; i < n; i++) {
            best = Math.max(best, inc[i] + dec[i] - 1);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] sample = {1, 11, 2, 10, 4, 5, 2, 1};
        System.out.println("Longest bitonic subsequence length: "
                + longestBitonicSubsequence(sample)); // 6
    }
}

Maximum-Sum Increasing Subsequence: same $O(n^2)$ shape as the original problem, but $dp[i]$ tracks the largest achievable sum of an increasing subsequence ending at $i$, not the largest achievable length. The base case becomes $dp[i] = arr[i]$ (a subsequence of just itself), and the transition is dp[i] = max(dp[i], dp[j] + arr[i]) for every $j < i$ with $arr[j] < arr[i]$; the answer is $\max_i dp[i]$.

6. Complexity Analysis

                Basic DP: $O(n^2)$ time, $O(n)$ space — every index compares against every earlier index. Patience sorting: $O(n \log n)$ time, $O(n)$ space — the outer loop is still $O(n)$, but each element now costs $O(\log n)$ binary-search work instead of an $O(n)$ linear scan. Reconstruction and counting: both ride on top of the $O(n^2)$ pass, so they do not change its asymptotic cost — they add only $O(n)$ extra space for the parent or count array.
            

The gap between $O(n^2)$ and $O(n \log n)$ is the same gap that separates a "correct first draft" from a "production-ready" algorithm: for $n$ in the low thousands both run instantly, but at $n = 10^6$ the quadratic version is not viable while the patience-sorting version still is. Reach for $O(n \log n)$ only when you need length alone at scale; reach for the $O(n^2)$-with-parent-pointers version whenever you need the actual elements, since patience sorting's fast path complicates reconstruction.

7. Applications and Alternatives

Where LIS shows up in practice

Box-stacking problems: given boxes with (width, height, depth), find the tallest stack where each box strictly fits inside the one below it — a multi-dimensional LIS after sorting by base area.
Russian Doll Envelopes: a classic 2D LIS variant — envelopes nest only if both dimensions strictly increase, so the problem reduces to sorting on one dimension and running LIS on the other (see the Medium exercise below).
Patience sorting's card-game origin: the same pile-building rule used to compute the LIS length is literally how the solitaire game of Patience is played by hand; the algorithm formalizes an intuition card players already have.

8. Exercises and Mastery

Easy

Using the $O(n^2)$ DP approach, find the LIS length of [3, 10, 2, 1, 20]. Write out the dp array by hand before checking it in code.

Medium

Russian Doll Envelopes: given a list of (width, height) pairs, find the maximum number that can be nested, where an envelope fits inside another only if both its width and height are strictly smaller. Sort the envelopes by width ascending, breaking ties by sorting height descending (this stops same-width envelopes from being nested inside each other), then run ordinary 1D LIS on the height sequence. Explain why the descending tie-break is necessary.

Hard

Extend the reconstruction technique from Section 5 to the Longest Bitonic Subsequence: track a forward parent array alongside $inc[i]$ and a backward parent array alongside $dec[i]$, then stitch the two chains together at the peak index that maximizes $inc[i] + dec[i] - 1$. Recover the actual sequence, not just its length, for [1, 11, 2, 10, 4, 5, 2, 1].

Mastery challenge: A log-processing service receives a stream of a million timestamped readings and must report the length of the longest increasing run of values, without storing the full stream in memory beyond what patience sorting already requires. Justify why the $O(n \log n)$ approach is the right choice here, and explain what additional information you would need to store if the service later asked for the actual reading values, not just the count.

Review rhythm: tomorrow, re-derive the $O(n^2)$ recurrence and the patience-sorting invariant from memory, without looking at the code; next week, implement reconstruction and counting from scratch on a new array; several weeks later, solve Russian Doll Envelopes and the bitonic reconstruction exercise without hints. Finally, teach someone why tails is not a real subsequence of the input.

9. Summary Cheat Sheet

$dp[i]$ = length of the LIS ending exactly at index $i$; the answer is $\max_i dp[i]$, not $dp[n-1]$.
Basic DP: $dp[i] = 1 + \max(dp[j])$ for $j < i$ with $arr[j] < arr[i]$ — $O(n^2)$ time.
Patience sorting: maintain tails, binary-search each new value's lower_bound position — $O(n \log n)$ time. tails is auxiliary, not a real subsequence.
Reconstruction needs a parent[i] array threaded through the $O(n^2)$ pass, then a backward walk from the best index.
Counting needs a parallel count[i] array: reset on strict improvement, accumulate on ties.
Longest Decreasing Subsequence: flip the comparison. Longest Bitonic Subsequence: combine $inc[i] + dec[i] - 1$. Maximum-Sum Increasing Subsequence: same recurrence shape, maximize sum instead of length.
Russian Doll Envelopes is 2D LIS in disguise: sort by one dimension (with a careful tie-break), then run 1D LIS on the other.

Cookie Consent

The Longest Increasing Subsequence Family

Table of Contents

1. Introduction and Motivation

2. A Concrete Example

Finding the LIS of [10, 9, 2, 5, 3, 7, 101, 18]

3. O(n²) DP Approach

4. O(n log n) Patience Sorting Method

5. Reconstructing the Actual LIS

Counting the Number of LIS

Variants: Decreasing, Bitonic, and Maximum-Sum Increasing Subsequences

6. Complexity Analysis

7. Applications and Alternatives

Where LIS shows up in practice

8. Exercises and Mastery

Easy

Medium

Hard

9. Summary Cheat Sheet

Cookie Consent

The Longest Increasing Subsequence Family

Table of Contents

1. Introduction and Motivation

2. A Concrete Example

Finding the LIS of [10, 9, 2, 5, 3, 7, 101, 18]

3. O(n²) DP Approach

4. O(n log n) Patience Sorting Method

5. Reconstructing the Actual LIS

Counting the Number of LIS

Variants: Decreasing, Bitonic, and Maximum-Sum Increasing Subsequences

6. Complexity Analysis

7. Applications and Alternatives

Where LIS shows up in practice

8. Exercises and Mastery

Easy

Medium

Hard

9. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 15: Core DP Patterns

Sequence DP: Edit Distance