DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

The one-line goal: Given an array, find the length of the longest subsequence (not contiguous!) whose elements are strictly increasing.

WHAT are we computing?

Example: A = [10, 9, 2, 5, 3, 7, 101, 18] → LIS = [2, 3, 7, 101] or [2, 3, 7, 18], length 4.

Approach 1 — DP in $O(n^2)$

for i in 0..n-1:
    dp[i] = 1
    for j in 0..i-1:
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp)

Cost: two nested loops → $O(n^2)$ time, $O(n)$ space.

Worked example Trace

A = [3, 1, 4, 1, 5]

i	A[i]	dp[i]	why
0	3	1	nothing before
1	1	1	3 ≮ 1, alone
2	4	2	extend 3 (dp=1) → 2; extend 1 → 2
3	1	1	nothing smaller before
4	5	3	extend 4 (dp=2) → 3

Answer = max = 3 (e.g. [3,4,5]). Why this step? At i=4, the best predecessor is index 2 (4, dp 2), so dp[4]=3.

Approach 2 — Patience sorting in $O(n \log n)$

Worked example Trace

A = [10, 9, 2, 5, 3, 7, 101, 18]

x	action	tails after
10	append	`[10]`
9	replace tails[0] (≥9)	`[9]`
2	replace tails[0]	`[2]`
5	append (5>2)	`[2,5]`
3	replace tails[1] (first ≥3 is 5)	`[2,3]`
7	append	`[2,3,7]`
101	append	`[2,3,7,101]`
18	replace tails[3] (first ≥18 is 101)	`[2,3,7,18]`

Length = 4. Why this step? At x=3, 3 fits where 5 was (length-2 tail), lowering it so future small values extend more easily — that's how [2,3,7,18] becomes reachable.

Figure — DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

Forecast-then-Verify

Recall Before reading the answer: for

A=[0,1,0,3,2,3], what's the LIS length and one such subsequence? Length 4: [0,1,2,3]. Check with tails: [0]→[0,1]→ (replace 0)[0,1]→[0,1,3]→(replace 3 with 2)[0,1,2]→[0,1,2,3]. ✓

Flashcards

What is the difference between a subsequence and a subarray?

Subarray is contiguous; subsequence is formed by deleting elements without reordering (can have gaps).

Define the DP state used in the O(n²) LIS solution.

dp[i] = length of the longest increasing subsequence ending exactly at index i.

State the O(n²) LIS recurrence.

dp[i] = 1 + max(0, {dp[j] : j<i and A[j]<A[i]}); answer = max over all dp[i].

Why is the final answer max(dp) and not dp[n-1]?

Because the LIS can end at any index, not necessarily the last one.

In the O(n log n) method, what does tails[k] store?

The smallest possible tail value of any increasing subsequence of length k+1.

Why is the tails array always strictly increasing?

Chopping a longer chain gives a shorter chain with a smaller tail, and tails[k] is the smallest such tail, so values must increase with length.

For each new x in patience sorting, what do you do?

lower_bound for first tails[k] >= x; replace it, or append x if x exceeds all tails.

Why use lower_bound (>=) instead of upper_bound (>) for strict LIS?

To avoid equal values forming a fake longer increasing chain; >= keeps it strictly increasing.

Does len(tails) equal the LIS length? Is tails the actual LIS?

len(tails) = correct LIS length; but tails itself is NOT a valid subsequence (need predecessor pointers to recover it).

What are the time complexities of the two LIS methods?

O(n²) DP, and O(n log n) with binary search over tails.

Recall Feynman: explain to a 12-year-old

Imagine stacking cards face-up in piles, left to right. Rule: a card can go on a pile only if it's bigger than that pile's top card, and you always put it on the leftmost pile where it fits — if it fits nowhere, start a brand-new pile to the right. The number of piles you end up with is the length of the longest "always-getting-bigger" line of cards you could pick! Each pile's top is kept as small as possible so more cards can stack on later. That "leftmost pile" choice is just the binary search.

Connections

Dynamic Programming — LIS is the classic 1D DP-on-suffix/prefix pattern.
Binary Search — lower_bound powers the O(n log n) speedup.
Patience Sorting — the card-pile model behind the fast method.
Longest Common Subsequence (LCS) — LIS(A) = LCS(A, sorted-unique(A)).
Greedy Algorithms — keeping smallest tails is a greedy exchange argument.
Russian Doll Envelopes — a 2D application built on LIS.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, LIS ka matlab hai: array me se kuch elements delete karke (order badle bina) ek aisi sequence banao jo strictly badhti jaye, aur uski sabse lambi length chahiye. Yaad rakho — subsequence me gaps allowed hain, subarray me nahi. Brute force me 2^n subsequences hote hain, isliye smart approach chahiye.

Pehla tareeka O(n^2) DP hai. Idea simple: dp[i] rakho = "index i pe khatam hone wali longest increasing subsequence ki length". Har i ke liye peeche dekho — jitne bhi j aise hain jahan A[j] < A[i], unme se best dp[j] uthao aur +1 kar do. Final answer = sabhi dp[i] ka max, kyunki LIS kahin bhi end ho sakti hai.

Doosra tareeka O(n log n) — yeh patience sorting wala jugaad hai. Ek tails array rakho jisme tails[k] = "length k+1 wali increasing subsequence ka sabse chhota possible last value". Har naye x ke liye binary search se pehla tails[k] >= x dhoondo: mil gaya to wahan x rakh do (tail chhota karke future me extend karna easy banaya), nahi mila to x ko append kar do (ek lambi chain ban gayi). Akhir me len(tails) hi LIS length hai. Important warning: tails khud asli subsequence NAHI hai — values overwrite hoti rehti hain — sirf uski length sahi hai. Strict LIS ke liye lower_bound (>=) use karo, taaki barabar values fake chain na bana de.

DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

WHAT are we computing?

Approach 1 — DP in $O(n^2)$

Approach 2 — Patience sorting in $O(n \log n)$

Forecast-then-Verify

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Algorithm Paradigms

Connections