Longest Increasing Subsequence

Longest Increasing Subsequence (LIS) works by tracking, for every possible subsequence length, the smallest tail value that can end a subsequence of that length — because a smaller tail always leaves more room to extend later, so you never need to remember more than one candidate per length.

Recognize the pattern

• Phrasing: "longest subsequence that is increasing / non-decreasing / strictly increasing", where elements may be skipped but original order must be kept.
• You are optimizing a length or count over an ordered sequence with a monotonic comparison condition.
• Brute force is "try every subset" (2^n) or "try every chain of pairs" (n^2) and the problem wants better.
• Reduces-to-LIS variants: longest non-decreasing run, minimum deletions to sort an array, Russian Doll Envelopes, box stacking, longest chain of pairs.

Brute force → optimal

Complexity, derived

O(n^2) DP. For each index i we scan all earlier indices j < i to test nums[j] < nums[i] and relax dp[i] = max(dp[i], dp[j]+1). Total comparisons = 0+1+2+...+(n-1) = n(n-1)/2 → O(n^2) time. One dp[] array of size n → O(n) space.

O(n log n) patience sorting. tails[] holds at most one value per achievable length, so its size is bounded by n. Each of the n elements does exactly one binary search over tails (size ≤ n) → n × O(log n) = O(n log n) time, O(n) space for tails[].

Worked example

nums = [10, 9, 2, 5, 3, 7, 101, 18]. Track tails[] (smallest tail per length) as we scan left to right, using binary search to find where each value belongs.

Final length = len(tails) = 4. Note tails = [2, 3, 7, 18] is a valid LIS here, but that's coincidental — tails is a bookkeeping array of best-known tail values, not guaranteed to be a real subsequence that occurred in that exact order (see Pitfalls).

Java (O(n log n))

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int lo = 0, hi = size; // binary search for first tails[i] >= x
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < x) lo = mid + 1; else hi = mid;
        }
        tails[lo] = x;
        if (lo == size) size++;
    }
    return size;
}

Pitfalls

• Treating tails[] as an actual subsequence: it is not reconstructible directly. To recover the real LIS elements, you must additionally store a predecessor index per element and backtrack (parent pointers), not just read tails[] off.
• Using the wrong binary search bound: strictly increasing needs "first index with tails[i] >= x" (lower_bound); non-decreasing needs "first index with tails[i] > x" (upper_bound). Swapping these silently breaks duplicate handling.
• Off-by-one when appending vs replacing: forgetting to grow size when lo == size gives a length that's short by one.
• Confusing this with Longest Common Subsequence (LCS) — a different two-sequence O(n*m) DP; LIS is single-sequence.

When to use / when not

Use patience sorting O(n log n) whenever n is large (thousands+) or you only need the length. Use the O(n^2) DP when n is small, you need the actual subsequence with simple bookkeeping, or the comparison condition is not a simple total order (e.g. LIS with additional constraints per element) where binary search doesn't directly apply.

Vs. LCS-based reduction: LIS can also be solved by sorting a copy, then running LCS(original, sorted-deduped) in O(n^2) or O(n log n) with coordinate compression + Fenwick tree — useful when the problem is stated as "LIS of one sequence relative to another's order" (e.g. minimum swaps problems). That reduction adds implementation complexity for no asymptotic win over patience sorting on a single sequence, so prefer patience sorting unless the two-sequence framing is natural.

Takeaways

• The key insight is greedy tail minimization: the smallest tail for a given length dominates any larger tail of the same length.
• tails[] length = LIS length, but tails[] itself is a proxy array, not the real answer sequence.
• O(n^2) DP generalizes more easily (arbitrary orderings, reconstruction); O(n log n) wins on raw speed for a plain increasing/non-decreasing condition.

Recall: Why does replacing tails[k] with a smaller value never shrink the final answer's correctness, even though tails is not itself a valid subsequence?

Sources: CLRS-style patience sorting analysis; LeetCode 300 (Longest Increasing Subsequence) constraints and examples.