Longest Increasing Subsequence — O(n²) Batch Timeout

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 (LIS)? — Plain English

The Longest Increasing Subsequence (LIS) problem: given an array of numbers, find the length of the longest subsequence where each element is strictly greater than the previous. Elements do not need to be contiguous.

Example: in [3, 1, 8, 2, 5], the LIS is [1, 2, 5] with length 3 (or [3, 8] is length 2, [1, 5] is length 2).

Real-world uses: scheduling problems where tasks must follow a precedence order, finding the maximum number of non-overlapping intervals that can be stacked, and as a building block for the patience sorting algorithm.

How Longest Increasing Subsequence (LIS) Works — Step by Step

O(n^2) DP approach: 1. Define dp[i] = length of the LIS ending at index i. 2. Initialize all dp[i] = 1 (each element is an LIS of length 1 by itself). 3. For each i from 0 to n-1: For each j from 0 to i-1: If arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) 4. Return max(dp).

O(n log n) Binary Search approach (patience sorting): 1. Maintain a 'tails' array where tails[i] = the smallest tail element of all increasing subsequences of length i+1. 2. For each number x in the array: - Binary search for the leftmost position in tails where tails[pos] >= x. - If no such position: append x to tails (extends the longest subsequence). - Else: replace tails[pos] with x (allows a better (smaller tail) subsequence of that length). 3. Return len(tails).

Worked Example — Tracing the Algorithm

Array: [3, 1, 8, 2, 5, 4, 6]. Find LIS.

O(n^2) DP trace: dp = [1, 1, 1, 1, 1, 1, 1] (start) i=0 (3): no j before. dp[0]=1. i=1 (1): j=0: arr[0]=3 > 1. No update. dp[1]=1. i=2 (8): j=0: 3<8, dp[2]=max(1,dp[0]+1)=2. j=1: 1<8, dp[2]=max(2,dp[1]+1)=2. dp[2]=2. i=3 (2): j=0: 3>2. j=1: 1<2, dp[3]=max(1,dp[1]+1)=2. j=2: 8>2. dp[3]=2. i=4 (5): j=0: 3<5, dp[4]=max(1,2)=2. j=1: 1<5, dp[4]=max(2,2)=2. j=2: 8>5. j=3: 2<5, dp[4]=max(2,3)=3. dp[4]=3. i=5 (4): j=3: 2<4, dp[5]=max(1,3)=3. dp[5]=3. i=6 (6): j=0: 3<6->2. j=3: 2<6->3. j=4: 5<6->4. j=5: 4<6->4. dp[6]=4. dp = [1, 1, 2, 2, 3, 3, 4]. max=4.

O(n log n) patience sort trace: x=3: tails=[3] x=1: 1 replaces 3. tails=[1] x=8: 8 > all. tails=[1,8] x=2: 2 replaces 8. tails=[1,2] x=5: 5 > all. tails=[1,2,5] x=4: 4 replaces 5. tails=[1,2,4] x=6: 6 > all. tails=[1,2,4,6] len(tails)=4. LIS length = 4 (e.g., [1,2,5,6] or [1,2,4,6]).

Implementation

The following implementation demonstrates Longest Increasing Subsequence (LIS) with clear comments.

import bisect

def lis_dp(arr):
    """O(n^2) DP approach"""
    n  = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0

def lis_binary(arr):
    """O(n log n) patience-sort approach"""
    tails = []
    for x in arr:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

def lis_reconstruct(arr):
    """O(n log n) with reconstruction"""
    tails = []
    indices = []  # index of tails[i] in original arr
    prev = [-1] * len(arr)
    for i, x in enumerate(arr):
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
            indices.append(i)
        else:
            tails[pos] = x
            indices[pos] = i
        # Link predecessor
        if pos > 0:
            prev[i] = indices[pos - 1]
        else:
            prev[i] = -1
    # Reconstruct by tracing back from last element of tails
    k = indices[-1]
    seq = []
    while k != -1:
        seq.append(arr[k])
        k = prev[k]
    seq.reverse()
    return len(seq), seq

arr = [3, 1, 8, 2, 5, 4, 6]
print('O(n^2) LIS:', lis_dp(arr))     # 4
print('O(n log n) LIS:', lis_binary(arr))  # 4
length, seq = lis_reconstruct(arr)
print('LIS length:', length, 'Sequence:', seq)  # 4 [1,2,4,6] or [1,2,5,6]

Edge Cases and Duplicate Handling

Strictly increasing vs non-decreasing: the bisect variant matters. - bisect_left: replaces first element >= x → ensures strict increase (duplicates not allowed to extend). - bisect_right: replaces first element > x → allows equal values to extend the subsequence (non-decreasing).

Negative numbers: the algorithm works with any comparable elements. No special casing needed.

Empty array: return 0.

Single element: return 1.

All decreasing: LIS length = 1.

All equal: LIS length = 1 (strict) or n (non-decreasing).

Large integers: Python's int is arbitrary precision — no overflow. In Java or C++, use long or BigInteger if applicable.

Why O(n log n) LIS Is Called Patience Sorting

The name comes from the card game of patience (solitaire). Imagine you have a deck of cards in random order. You create piles by placing each card on the leftmost pile whose top card is >= the current card. If no pile qualifies, start a new pile on the right. The number of piles after processing all cards is the LIS length.

This isn't just an analogy — the algorithm was discovered by D.E. Knuth and friends in the 1960s while studying patience sorting, and it directly translates to the tails array.

Why it works: The piles maintain the invariant that the top cards are sorted in increasing order (left to right). Each new card either extends the chain (creates a new pile) or improves an existing pile by lowering its top card. The length of the longest chain is always the number of piles.