Longest Increasing Subsequence — O(n²) Batch Timeout

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.

The Recursive Decomp — Why Brute Force Gets You Fired

Before we get clever with binary search, understand the cost of naivety. The recursive approach reads like a textbook: for each element at index i, look left for every smaller element, recursively compute their LIS, take max, add 1. Problem? You're recomputing the same subproblems across overlapping branches—exponential complexity in real terms.

For an array of 40 elements, you're looking at over a trillion recursive calls. That's not an edge case, that's a production outage waiting to happen. Every recursive call spawns a new stack frame, and for any real dataset (think: financial time series, log sequences), this burns through memory and time simultaneously.

The formula looks clean: L(i) = 1 + max(L(prev)) for all prev < i with arr[prev] < arr[i]. But clean on paper means nothing when your monitoring dashboard is red. Recursion is a learning tool, not a deployment strategy.

// io.thecodeforge — dsa tutorial

public class LISRecursive {
    public static int lengthOfLIS(int[] sequence) {
        return solve(sequence, Integer.MIN_VALUE, 0);
    }

    private static int solve(int[] seq, int lastValue, int currentIndex) {
        if (currentIndex == seq.length) {
            return 0;
        }
        int exclude = solve(seq, lastValue, currentIndex + 1);
        int include = 0;
        if (seq[currentIndex] > lastValue) {
            include = 1 + solve(seq, seq[currentIndex], currentIndex + 1);
        }
        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        int[] data = {3, 10, 2, 1, 20};
        System.out.println("LIS length: " + lengthOfLIS(data));
    }
}

Memoization — Buying Time by Storing What You Already Paid For

You identified the waste. Now fix it. Memoization caches results for each (index, lastValue) pair—but here's the twist: lastValue is unbounded, so you index by the previous element's position instead. This gives O(n^2) time and O(n^2) space. Still quadratic, but the difference between 2^40 and 40^2 is the difference between a coffee break and a termination meeting.

The trick: dp[i][prev] or, more practically, a 1D array where memo[i] stores the LIS length ending at index i. Fill it top-down with recursion but consult the cache before branching. This transforms your exponential mess into something that actually finishes before your CI pipeline times out.

Memoization shines when only a subset of states are reachable—but for LIS? Every element is a potential start or end. You're still paying O(n^2) in the worst case. It's better, but not production-grade for large sequences. Use this as a stepping stone to the bottom-up DP, not as your final answer.

// io.thecodeforge — dsa tutorial

import java.util.Arrays;

public class LISMemoization {
    public static int lengthOfLIS(int[] sequence) {
        int n = sequence.length;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, solve(sequence, i, memo));
        }
        return maxLen;
    }

    private static int solve(int[] seq, int current, int[] memo) {
        if (memo[current] != -1) return memo[current];
        int best = 1;
        for (int prev = 0; prev < current; prev++) {
            if (seq[prev] < seq[current]) {
                best = Math.max(best, 1 + solve(seq, prev, memo));
            }
        }
        memo[current] = best;
        return best;
    }

    public static void main(String[] args) {
        int[] data = {3, 10, 2, 1, 20};
        System.out.println("LIS length: " + lengthOfLIS(data));
    }
}

Bottom-Up DP — Tabulate or Die Trying

Recursion with memoization still carries recursion overhead. For a function called 40 million times, those stack frames add up. Bottom-up DP eliminates that entirely: iterate left to right, maintain a dp[i] array where each entry is the LIS length ending at index i. For each i, scan all j < i, check if arr[j] < arr[i], and set dp[i] = max(dp[i], dp[j] + 1).

Code's shorter. Performance is predictable. No recursion limits, no stack overflow in production. Time is still O(n^2), but space collapses to O(n). This is the version you ship to staging for validation before switching to the O(n log n) Patience Sorting version.

Watch your edge cases: all equal elements? Prep dp with 1 for each position. Duplicates? The strict < comparison handles it—if you see arr[j] == arr[i], skip it. This is where junior devs introduce bugs by using <= instead of <. One character, and your LIS magically includes duplicates, inflating your metric. Measure twice, deploy once.

// io.thecodeforge — dsa tutorial

public class LISBottomUp {
    public static int lengthOfLIS(int[] sequence) {
        int n = sequence.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (sequence[j] < sequence[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] data = {3, 10, 2, 1, 20};
        System.out.println("LIS length: " + lengthOfLIS(data));
    }
}

Generalize the Relationship — LIS Is Hiding in Plain Sight

You think LIS is just about numbers? Wrong. LIS is a pattern for any sequence where order matters and you're looking for the longest chain that respects a comparator. Once you see that, LIS stops being a puzzle and becomes a weapon.

The core relationship is simple: for every element at index i, the longest increasing subsequence ending at i is 1 plus the maximum LIS ending at any previous index j where arr[j] < arr[i]. That's not just for integers — it works for strings, tuples, or any comparable type. The comparator defines "increasing".

In production, this generalizes to problems like "longest chain of boxes that fit inside each other" or "maximum number of events you can attend without overlap". You sort by one dimension, then run LIS on the other. Same DP. Same O(n log n) time when you optimize. Stop memorizing problems — generalize the relationship and watch the grind melt away.

// io.theforge — dsa tutorial

import java.util.*;

public class GeneralizedLIS {
    // Generic LIS for any Comparable type
    public static <T extends Comparable<T>> int lengthOfLIS(List<T> arr) {
        List<T> tails = new ArrayList<>();
        for (T x : arr) {
            int pos = Collections.binarySearch(tails, x);
            if (pos < 0) pos = -(pos + 1);
            if (pos == tails.size()) tails.add(x);
            else tails.set(pos, x);
        }
        return tails.size();
    }

    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(3, 1, 8, 2, 5);
        System.out.println(lengthOfLIS(arr));  // Output: 3
    }
}

Step-by-Step: Trace [3, 1, 8, 2, 5] — Watch the Tails Grow

Stop reading abstract theory. Let's walk the classic O(n log n) tails algorithm on [3, 1, 8, 2, 5] so you see exactly why it works.

Length of tails at end = 3. That's the LIS length. Notice tails is NOT the actual subsequence — it's the smallest possible tail of an increasing subsequence of each length. When you replace 8 with 2, you're saying "an LIS of length 2 can end at 2 instead of 8", which opens the door for 5 to extend to length 3.

This is not magic. It's greedy optimization: keep the lowest possible ending value for each subsequence length so future elements have the best chance to extend it.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class TraceLIS {
    public static void main(String[] args) {
        int[] arr = {3, 1, 8, 2, 5};
        List<Integer> tails = new ArrayList<>();
        
        for (int x : arr) {
            int pos = Collections.binarySearch(tails, x);
            if (pos < 0) pos = -(pos + 1);
            if (pos == tails.size()) tails.add(x);
            else tails.set(pos, x);
            System.out.println("After " + x + ": tails = " + tails);
        }
        System.out.println("LIS length: " + tails.size());
    }
}