Longest increasing subsequence, edit distance and other sequence DPs

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Coin ways loop order for combinations? from Lesson 5.2.2
• Number of parenthesisations of 5 matrices? from Lesson 5.2.1
• LCS on a match? from Lesson 5.1.3

1 · The Hook

🎣

Spell-checkers suggest the word with the smallest edit distance; stock analysts look for the longest increasing run of prices, not necessarily consecutive. Both are sequence DPs that GATE uses, and both reuse the LCS pattern you know.

2 · Predict First

🤔

Longest strictly increasing subsequence of [10, 9, 2, 5, 3, 7, 101, 18]?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

4: for example 2, 5, 7, 101 (or 2, 3, 7, 18).

Longest increasing subsequence (LIS)

L[i] = length of the longest increasing subsequence ending at A[i].

• L[i] = 1 + max { L[j] : j < i, A[j] < A[i] } (or 1 if none).
• Answer = max over i of L[i]. Θ(n²).
• A cleverer method (patience sorting with binary search) runs in Θ(n log n).
• LIS of A = LCS of A and sorted(A) (for distinct values).

Edit distance (Levenshtein)

Minimum number of insertions, deletions and substitutions turning string a into b. D[i][j] = distance between a[1..i] and b[1..j]:

• D[i][0] = i; D[0][j] = j.
• D[i][j] = min( D[i − 1][j] + 1 (delete), D[i][j − 1] + 1 (insert), D[i − 1][j − 1] + [aᵢ ≠ bⱼ] (substitute or match) ).

Θ(mn). kitten → sitting: 3 (k→s, e→i, insert g).

Other DPs to recognise

• Kadane (maximum subarray): Θ(n).
• Number of BSTs on n keys: Catalan Cₙ (1, 2, 5, 14, 42).
• Floyd–Warshall and Bellman–Ford (Phase 6) are DPs on paths.
• Optimal BST: interval DP like matrix chain, Θ(n³).

4 · Visual

LIS on [10, 9, 2, 5, 3, 7, 101, 18]

i:      1    2    3    4    5    6    7    8
A:     10    9    2    5    3    7  101   18
L:      1    1    1    2    2    3    4    4      answer = max L = 4

5 extends 2; 7 extends 5 or 3; 101 and 18 both extend 7

Edit-distance table for kitten (rows) into sitting (columns); the answer is the bottom-right entry.

5 · Worked Examples

Example 1 Easy

LIS length of [3, 10, 2, 1, 20]?

Solution

3, 10, 20: 3.

Example 2 Medium

Edit distance between sunday and saturday?

Solution

Insert a, insert t, substitute n → r: 3.

Example 3 GATE

Number of structurally distinct BSTs on 4 distinct keys?

Solution

Catalan C₄ = 14.

6 · GATE Traps

⚠️

• L[i] is the LIS ending at i; the answer is the max over i, not L[n].
• "Increasing" usually means strictly; check the question.
• Edit distance borders are D[i][0] = i and D[0][j] = j, not zeros.
• A match costs 0 on the diagonal; a mismatch costs 1.

7 · Memory Hook

🧠

"LIS: best ending here. Edit: delete, insert, or swap."

8 · Connect the Dots

Phase 5 is complete. Phase 6, the last content phase, runs on graphs: traversals, minimum spanning trees and shortest paths, where you will meet greedy (Prim, Kruskal, Dijkstra) and DP (Bellman–Ford, Floyd–Warshall) again.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markLIS

LIS length of [5, 2, 8, 6, 3, 6, 9, 7]?

Numerical answer: ________

Q2NAT2 marksLIS

LIS length of [0, 8, 4, 12, 2, 10, 6, 14, 1, 9]?

Numerical answer: ________

Q3NAT2 marksEdit distance

Edit distance between horse and ros?

Numerical answer: ________

Q4NAT1 markCatalan

Number of distinct BSTs on 5 distinct keys?

Numerical answer: ________

Q5MCQ1 markLIS time

The simple DP for LIS runs in:

• (A) Θ(n)
• (B) Θ(2ⁿ)
• (C) Θ(n log n)
• (D) Θ(n²)

10 · Rule Card

• LIS: L[i] = 1 + max L[j] (j < i, A[j] < A[i]); answer max L[i]; Θ(n²) (n log n possible).
• Edit distance: min(delete, insert, substitute/match); borders i and j; Θ(mn).
• BSTs on n keys: Catalan Cₙ.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

longest increasing subsequenceLIS ending at iedit (Levenshtein) distanceinsert, delete, substitutenumber of BSTs (Catalan)optimal BST (named)

12 · Answer Vault