Longest Increasing Subsequence: O(n log n) Deep Dive with DP

The Longest Increasing Subsequence (LIS) problem shows up everywhere you need to measure 'how ordered can this data get?' — from DNA sequence alignment in bioinformatics, to version-conflict resolution in distributed systems, to patience sorting algorithms used in real card games. It's deceptively simple to describe but hides serious algorithmic depth. Companies like Google, Meta, and Jane Street use it as a litmus test for whether a candidate truly understands dynamic programming versus just memorising patterns.

The core challenge: given an unsorted array of numbers, find the length (and elements) of the longest subsequence where every element is strictly greater than the previous one. The tricky part is 'subsequence' — you don't need contiguous elements. You can skip as many elements as you like, as long as the ones you pick stay in their original left-to-right order and keep going up. A brute-force check of all 2^n subsets is obviously off the table for anything real-world sized.

By the end of this article you'll understand not one but two fundamentally different approaches — the classic O(n²) DP table and the elegant O(n log n) patience-sort algorithm — know how to reconstruct the actual subsequence (not just its length), handle tricky edge cases like duplicates and negative numbers, and walk into an interview ready to explain the why behind every decision, not just recite the code.

What is Longest Increasing Subsequence?

Longest Increasing Subsequence is a core concept in DSA. Rather than starting with a dry definition, let's see it in action and understand why it exists.

// TheCodeForge — Longest Increasing Subsequence example
// Always use meaningful names, not x or n
public class ForgeExample {
    public static void main(String[] args) {
        String topic = "Longest Increasing Subsequence";
        System.out.println("Learning: " + topic + " 🔥");
    }
}

Frequently Asked Questions