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

3.7.11 · D3 · Coding › Algorithm Paradigms › DP problems — Longest Increasing Subsequence (LIS) — O(n²) a

Shuru karne se pehle, dono tools ki ek reminder plain words mein:

Recall Dono machines ek hi saanp mein

DP machine: dp[i] = sabse lambi strictly-increasing chain ki length jo exactly index i pe khatam hoti hai. Ise left to right bharo; answer dp mein kahi bhi sabse bada value hai. Tails machine: tails[k] = sabse chhhota value jo length k+1 ki chain ko khatam kar sakta hai. Har naye x ke liye, sabse pehla tails[k] >= x dhoondo aur overwrite karo; agar koi nahi, toh append karo. Answer = len(tails).

The scenario matrix

Har array jo tum kabhi bhi LIS ko de sakte ho, woh in cells mein se ek mein aata hai. Agar tum sab kar sako, toh tum ne sab kuch dekh liya.

Cell	Input shape	Kya tricky hai	Example ex.
C1	Already sorted (strictly increasing)	LIS = poora array; har baar append, koi replace nahi	Ex 1
C2	Reverse sorted (strictly decreasing)	LIS = 1; har element `tails[0]` ko replace karta hai	Ex 2
C3	All equal	strict LIS = 1; ties extend NAHI hone chahiye	Ex 3
C4	Degenerate size — empty / one element	length 0 aur 1; loops ki boundary	Ex 4
C5	Ties in the middle (real growth ke saath mixed)	`>=` vs `>` yahan matter karta hai	Ex 5
C6	General zig-zag ("normal" case)	dono machines agree karni chahiye	Ex 6
C7	Negative numbers + plateau	signs matter nahi karte, sirf order karta hai	Ex 7
C8	Word problem (real-world)	ek story ko array mein convert karna	Ex 8
C9	Exam twist — non-decreasing LIS	`lower_bound`→`upper_bound` swap karo	Ex 9
C10	Actual sequence reconstruct karo	`tails` akela nahi kar sakta; parents chahiye	Ex 10

Ab hum har cell cover karte hain.

C1 — Already sorted (Ex 1)

Worked example Ex 1 —

A = [1, 2, 3, 4, 5] Forecast: aage padhne se pehle LIS length guess karo. Sorted increasing... kitna iska increasing subsequence hai?

Step 1 — DP. Har pehle wala element baad wale se chhhota hai, toh dp[i] = dp[i-1] + 1. dp = [1, 2, 3, 4, 5]. Yeh step kyun? Index i ke liye, best predecessor j hamesha i-1 hota hai (sabse bada dp[j]), aur $A [j] < A [i]$ sab j<i ke liye hold karta hai — toh chain bas badhti rehti hai.

Step 2 — Tails. Har x tails mein sab se bada hota hai, toh hum har baar append karte hain. [1] → [1,2] → [1,2,3] → [1,2,3,4] → [1,2,3,4,5]. Yeh step kyun? Koi tails[k] >= x kabhi nahi hota, toh "replace" branch kabhi fire nahi hota. len(tails)=5.

Verify: poora array already strictly increasing hai, toh LIS wahi array hai → length 5. Dono machines agree. ✓

C2 — Reverse sorted (Ex 2)

Worked example Ex 2 —

A = [5, 4, 3, 2, 1] Forecast: koi bhi do elements left-to-right "upar" nahi jaate. Longest increasing chain kya ho sakti hai?

Step 1 — DP. Koi bhi pehle wala element chhhota nahi, toh koi dp[j]+1 kabhi nahi jeetta. Har dp[i] = 1. dp = [1, 1, 1, 1, 1]. Yeh step kyun? Condition A[j] < A[i] har pair ke liye false hai (5>4>3...), toh predecessors pe max empty hai → dp[i] = 1 + 0 = 1.

Step 2 — Tails. Har naya x single tail se chhhota hai, toh woh har baar tails[0] ko replace karta hai. [5] → [4] → [3] → [2] → [1]. Yeh step kyun? lower_bound hamesha tails[0] >= x dhoondhta hai, toh hum overwrite karte hain. Length 1 se zyada kabhi nahi badhti.

Verify: koi bhi single element length 1 ka increasing subsequence hai, aur usse lamba koi nahi hai → 1. Dono agree. ✓ Yeh LIS length ke liye worst case hai, "smallest tails" churn ke liye best case.

C3 — All equal (Ex 3)

Worked example Ex 3 —

A = [7, 7, 7, 7] (strict LIS) Forecast: equal "increasing" NAHI hai. Toh answer kya hai — 4 ya 1?

Step 1 — DP. Humein A[j] < A[i] strictly chahiye. Lekin $7 < 7$ false hai. Toh koi bhi predecessor qualify nahi karta. dp = [1, 1, 1, 1]. Yeh step kyun? Strict LIS equal neighbours forbid karta hai; recurrence ka < filter unhe sab throw out karta hai.

Step 2 — Tails with lower_bound (>=). x=7 ke liye: kya koi tails[k] >= 7 hai? Pehle append ke baad tails=[7], haan — tails[0]=7 >= 7, toh hum replace karte hain (7 ko 7 se overwrite, koi growth nahi). [7] → [7] → [7] → [7]. lower_bound kyun yahan? >= use karne se ek equal value same slot pe land karti hai, kabhi append nahi hoti. Yahi woh hai jo ties ko fake longer chain banane se rokta hai.

Verify: sab-7's mein longest strictly increasing chain ek element hai → 1. Dono agree. ✓ (Contrast: agar problem non-decreasing maangti, toh answer 4 hota — C9 dekho.)

C4 — Degenerate sizes (Ex 4)

C5 — Ties in the middle (Ex 5)

Worked example Ex 5 —

A = [1, 3, 3, 4] (strict LIS) Forecast: do 3's ek row mein baithe hain. Kya LIS dono use karta hai, ek, ya koi nahi?

Step 1 — DP.

i	A[i]	dp[i]	kyun
0	1	1	pehla
1	3	2	1 extend karo (dp=1)
2	3	2	$3 < 3$ false, toh 2nd 3 1st pe nahi baith sakta; best predecessor `1` hai → dp=2
3	4	3	koi bhi 3 extend karo (dp=2) → 3
Yeh step kyun? Strict `<` `A[1]=3` ko `A[2]=3` ka predecessor banne se rokta hai, toh dono 3's independently dp=2 rakhte hain.

Step 2 — Tails (lower_bound). x=1 → [1]. x=3 → append → [1,3]. x=3 → leftmost tails[k] >= 3 hai tails[1]=3, replace karo (3→3, koi growth nahi) → [1,3]. x=4 → append → [1,3,4]. len = 3. Yeh step kyun? Doosra 3 pehle wale ki same slot pe land karta hai — [1,3,3] jaisi fake length-3 chain nahi banati.

Verify: longest strictly increasing hai [1,3,4] → 3. Dono agree. ✓

C6 — General zig-zag (Ex 6)

Worked example Ex 6 —

A = [3, 1, 4, 1, 5, 9, 2, 6] Forecast: ek lamba increasing chain eyeball karo, phir count karo.

Step 1 — DP.

i	A[i]	dp[i]	best predecessor
0	3	1	—
1	1	1	koi chhhota nahi
2	4	2	idx 0 (`3`, dp 1) ya idx 1 (`1`, dp 1)
3	1	1	koi chhhota nahi
4	5	3	idx 2 (`4`, dp 2)
5	9	4	idx 4 (`5`, dp 3)
6	2	2	idx 1 ya 3 (`1`, dp 1)
7	6	4	idx 4 (`5`, dp 3) — idx 5 nahi, kyunki $A [5] = 9 > 6$

answer = max(dp) = 4. Yeh step kyun? Hum best chain ending at each i record karte hain; global max winner chunti hai ([1,4,5,9] ya [1,4,5,6]). Note karo i=7 pe predecessor 6 se chhhota hona chahiye, toh 9 disqualify ho jaata hai aur chain index 4 pe 5 se hook back karti hai.

Step 2 — Tails. 3→[3], 1→[1], 4→[1,4], 1→[1,4], 5→[1,4,5], 9→[1,4,5,9], 2→[1,2,5,9], 6→[1,2,5,6]. len = 4. Yeh step kyun? 2 quietly tails[1] ko 4 se 2 kar deta hai — bookkeeping, real subsequence nahi — options open rakhta hai. Length 4 rehti hai.

Verify: dono 4 dete hain. ✓

Neeche wala figure padho. Har blue box ek array element hai (andar uski value, upar index i, neeche yellow mein dp[i]). Ek colored arrow har element se uske chosen predecessor tak jaata hai — woh j jo dp[i] set karta hai. Green-ringed boxes [3,4,5,9] follow karo: woh ek optimal length-4 chain hai, aur tum uske arrows left mein chain hote dekh sakte ho 9→5→4→3. Notice karo index 7 (6) ka index 5 (9) ki taraf koi arrow nahi — figure "9 is too big to precede 6" wali fact ko visible banata hai.

C7 — Negatives with a plateau (Ex 7)

Worked example Ex 7 —

A = [-2, -1, -1, 0, -3, 5] (strict LIS) Forecast: negatives scary lagte hain, lekin LIS sirf order ki parwah karta hai, sign ki nahi. Length guess karo.

Step 1 — DP.

i	A[i]	dp[i]	kyun
0	-2	1	pehla
1	-1	2	-2 extend karo
2	-1	2	$- 1 < - 1$ false; best -2 hai → 2
3	0	3	koi bhi -1 extend karo
4	-3	1	kuch chhhota nahi
5	5	4	0 extend karo (dp 3)
Yeh step kyun? `<` `-2 < -1 < 0 < 5` ko exactly positives ki tarah treat karta hai; tie `-1,-1` block ho jaati hai, dip `-3` ek chain restart karta hai.

Step 2 — Tails. -2→[-2], -1→[-2,-1], -1→[-2,-1] (replace), 0→[-2,-1,0], -3→[-3,-1,0] (tails[0] replace), 5→[-3,-1,0,5]. len = 4. Yeh step kyun? -3 length-1 tail ko lower karta hai — harmless, chain length 4 pe rakhta hai.

Verify: longest strict chain hai [-2,-1,0,5] → 4. Dono agree. Sign irrelevant hai; sirf relative order count karta hai. ✓

C8 — Word problem (Ex 8)

Worked example Ex 8 — Movie marathon

Tumhare paas movies hain jinke running times (minutes) us order mein hain jis order mein woh shelf pe appear hote hain: T = [90, 120, 100, 150, 130, 200]. Tum shelf se left to right movies pick karna chahte ho taaki har ek pichli se strictly longer ho (suspense build karte hue). Zyada se zyada kitni movies tum order mein dekh sakte ho?

Forecast: yeh LIS disguise mein hai — "increasing" quantity running time hai. Count guess karo.

Step 1 — Model karo. "Left to right pick karo, har ek strictly longer" = T ka strictly increasing subsequence. Toh LIS run karo. Yeh step kyun? "Original order rakho + har baar strictly bada" literally LIS ki definition hai; koi naya algorithm nahi chahiye.

Step 2 — Tails. 90→[90], 120→[90,120], 100→[90,100] (120 replace), 150→[90,100,150], 130→[90,100,130] (150 replace), 200→[90,100,130,200]. len = 4. Yeh step kyun? Tails lower karna (120→100, 150→130) 200 ke liye ek lambi chain extend karne ki jagah banata hai: [90,100,130,200].

Verify (units): 4 movies, lengths minutes mein 90 < 100 < 130 < 200 — strictly increasing ✓. Answer 4 movies.

C9 — Exam twist: non-decreasing LIS (Ex 9)

Worked example Ex 9 — Same

A = [1, 3, 3, 4], lekin ab non-decreasing (equal allowed hai) Forecast: C5 mein strict ne 3 diya. Equals allow hone par, kya dono 3's ab count honge?

Step 1 — Rule badlo. Non-decreasing matlab DP filter mein A[j] <= A[i], aur tails mein hum upper_bound pe switch karte hain (pehla tails[k] > x). Yeh step kyun? Strict LIS >= use karta hai toh tie same slot pe overwrite hoti hai; non-decreasing mein tie ko append karne ki zaroorat hai, jo exactly > x (equals ko skip) karta hai.

Step 2 — DP run (non-decreasing).

i	A[i]	dp[i]	kyun
0	1	1	pehla
1	3	2	$1 \leq 3$ → 1 extend karo (dp 1)
2	3	3	ab $3 \leq 3$ allowed hai → idx 1 extend karo (dp 2) → 3
3	4	4	$3 \leq 4$ → idx 2 extend karo (dp 3) → 4
Yeh step kyun? C5 se sirf change `<` ka `<=` banana hai; woh single edit doosre 3 ko pehle pe stack karne deta hai, `dp[2]` ko 2 se 3 uthata hai aur `dp[3]=4` tak cascade karta hai.

Step 3 — Tails with upper_bound. x=1 → [1]. x=3 → koi tail >3 nahi → append → [1,3]. x=3 → pehla tail >3? koi nahi (1,3 dono <=3 hain) → append → [1,3,3]. x=4 → append → [1,3,3,4]. len = 4. Yeh step kyun? Ab [1,3,3,4] length 4 ki ek legal non-decreasing chain hai.

Verify: non-decreasing longest = [1,3,3,4] → 4 (vs strict = 3). Dono machines agree; single >=↔> (aur <↔<=) swap answer flip karta hai. ✓

C10 — Actual subsequence reconstruct karo (Ex 10)

Worked example Ex 10 —

A = [3, 1, 4, 1, 5, 9, 2, 6] ke liye sirf length nahi, sequence recover karo Forecast: parent ne warn kiya tha ki tails akela real chain nahi de sakta. Hum kya extra store karte hain?

Step 1 — DP table + parent pointers use karo. C6 se, dp = [1,1,2,1,3,4,2,4]. parent[i] = woh j store karo jo dp[i] ko uski value deta hai (ya -1). parent = [-1, -1, 0, -1, 2, 4, 1, 4]. Yeh step kyun? dp yaad rakhta hai kitna lamba, parent yaad rakhta hai kahan se — saath mein yeh humein backwards walk karne deta hai.

Step 2 — Argmax se backtrack karo. max(dp)=4 pehli baar index 5 pe aata hai (A[5]=9). Parents follow karo: 5 → 4 → 2 → 0, yaani indices [0,2,4,5], values [3,4,5,9]. Yeh step kyun? Har parent hop optimal chain ka last element peel karta hai, use reveal karne ke liye reverse karta hai.

Verify: 3 < 4 < 5 < 9, length 4, C6 ki length se match karta hai. ✓ Note karo tails end mein [1,2,5,6] tha — values ka ek alag set (real subsequence bhi nahi), jo prove karta hai ki tumhe parent rakhna chahiye, tails se nahi padhna chahiye.

Coverage check

Recall Kya humne matrix ki har cell hit ki?

C1 sorted (Ex 1) ✓ · C2 reverse (Ex 2) ✓ · C3 all-equal (Ex 3) ✓ · C4 empty/singleton (Ex 4) ✓ · C5 mid ties (Ex 5) ✓ · C6 zig-zag (Ex 6) ✓ · C7 negatives+plateau (Ex 7) ✓ · C8 word problem (Ex 8) ✓ · C9 non-decreasing twist (Ex 9) ✓ · C10 reconstruction (Ex 10) ✓. Har woh scenario jo yeh topic throw kar sakta hai, ab kaam kiya ja chuka hai.

Connections

Dynamic Programming — har C-cell dp[i] ends-at-i state se solve hua.
Binary Search — lower_bound (C1–C8) vs upper_bound (C9) poora strict/non-decreasing switch hai.
Patience Sorting — upar wale tails traces literal card-pile runs hain.
Greedy Algorithms — "sabse chhhota tail rakho" ne har replace step justify kiya.
Russian Doll Envelopes — C10 ki reconstruction woh skill hai jo tum wahan reuse karte ho.
Longest Common Subsequence (LCS) — non-decreasing LIS (C9) sorted-with-duplicates ke saath LCS ke barabar hai.