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

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

Intuition Do mental pictures jo neeche har question ke peeche hain

Ye sketches apne dimag mein rakho — questions inhe hi pokte hain.

Picture 1 — "end-here DP" (the $O (n^{2})$ method). Array ko dots ki ek row ki tarah draw karo. dp[i] fill karne ke liye, tum leftward har pehle dot j ko dekhte ho jo dot i se chhota hai, aur unme se sabse lambi chain par khade hote ho, phir i par step up karte ho. Ye Dynamic Programming hai: j par khatam hone wali chhoti problem solve karo, use i par khatam hone wali badi problem ke liye reuse karo.

Picture 2 — "card piles" (Patience Sorting, the $O (n lo g n)$ method). Cards ko left se right deal karo piles mein. Ek card sirf us pile par baithta hai jiska top usse bada ho, aur hamesha use leftmost pile par daalo jo use accept kare; agar koi nahi karta, to right par ek nayi pile shuru karo. tails[k] bas pile k ka top card hai. Piles ki sankhya = LIS length. Leftmost pile choose karna exactly wahi kaam karta hai jo Binary Search karta hai — aur top ko hamesha chhote se chhota rakhna ek greedy choice hai (dekho Greedy Algorithms): hum tail ko chhota banane ka kabhi pachtava nahi karte, kyunki chhota top sirf zyada cards ko baad mein land karne deta hai.

True or false — justify

TRUE or FALSE: LIS array ka ek contiguous block hona chahiye.

FALSE. LIS subsequences par kaam karta hai, isliye elements skip ho sakte hain; e.g. [10,9,2,5,3,7] mein LIS [2,5,7] non-contiguous hai.

TRUE or FALSE: Strict LIS mein, pehle chosen value ke barabar koi value chain extend kar sakti hai.

FALSE. "Strictly increasing" equal neighbours ko forbid karta hai, isliye [2,2,3] mein LIS length 2 hoti hai, 3 nahi.

TRUE or FALSE: Ant mein len(tails) hamesha true LIS length ke barabar hoti hai.

TRUE. Length provably correct hai chahe tails ke contents koi real subsequence na hon.

TRUE or FALSE: Final array tails khud ek valid longest increasing subsequence hai.

FALSE. tails per-length bookkeeping hai jiske entries out of context overwrite ho chuke hain; ek real LIS recover karne ke liye predecessor pointers chahiye.

TRUE or FALSE: DP ka answer hamesha dp[n-1] (last index) hota hai.

FALSE. LIS kahin bhi khatam ho sakti hai, isliye answer saare dp[i] ka max hota hai; dp[n-1] tabhi sahi hai jab optimum coincidentally last pe khatam ho.

TRUE or FALSE: Algorithm ke dauran tails hamesha strictly increasing rakha jata hai.

TRUE. Lambi chain ko chhoti karne se chhoti tail aati hai, aur tails[k] aisi sabse chhoti tail hai, jo tails ko length ke saath increase karne par majboor karta hai.

TRUE or FALSE: tails mein ek entry replace karna kabhi bhi uski length badal sakta hai.

FALSE. Replacement ek existing slot ko in place overwrite karta hai; sirf ek append length ko ek se badhata hai.

TRUE or FALSE: Agar array already strictly increasing hai, to dono methods n return karte hain.

TRUE. Har element chain extend karta hai, isliye dp 1,2,...,n tak badhta hai aur har x tails mein append hota hai.

TRUE or FALSE: Agar array strictly decreasing hai, to LIS length 1 hoti hai.

TRUE. Koi element pehle wale se bada nahi hota, isliye har element akela khada rehta hai; har x bas tails[0] ko replace karta hai.

TRUE or FALSE: Array ko reverse karne se LIS length unchanged rehti hai.

FALSE in general.

A

ko reverse karne se uski LIS original ki longest decreasing subsequence ban jaati hai, aur in dono lengths ka match karna zaroori nahi — e.g. [1,2,4,3] ki LIS length 3 hai lekin uske reverse [3,4,2,1] ki LIS length 2 hai.

TRUE or FALSE:

O (n lo g n)

method mein bilkul bhi dynamic programming ideas use nahi hote, sirf ek greedy rule hota hai.

FALSE. Iska "keep the smallest tail" rule ek greedy exchange argument hai (dekho Greedy Algorithms), lekin ye phir bhi DP ki tarah per-length optimal sub-results reuse karta hai; ye bas DP inner loop ko Binary Search se replace karta hai.

Spot the error

Koi claim karta hai ki dp[i] ka matlab hai "index i tak ke poore array ka LIS". Ye subtly galat kyun hai?

dp[i] ko exactly i par khatam hona chahiye (A[i] ko apna last element use karte hue); "up to i" ek prefix maximum hoga, jo ek alag, weaker quantity hai.

Koi recurrence ko dp[i] = dp[i-1] + 1 likhta hai. Kya toot jaata hai?

Ye maanta hai ki previous index hi predecessor hai; predecessor actually sabse achha pehle wala j hota hai jahan A[j] < A[i] ho, jo zaroor i-1 nahi hoga.

Koi strict LIS ke liye upper_bound (first > x) use karta hai. Kya galat ho jaata hai?

Tab equal values append ho jaati hain replace hone ki jagah, ek fake longer "increasing" chain banaati hain jaise [2,2] ko length 2 count karna.

Koi x ko tails mein append karta hai jab bhi exact match nahi milta. Bug kya hai?

Append tabhi karo jab x saare tails se zyada ho; warna pehle >= x wale ko replace karo. Kisi bhi "not exact" par append karna algorithm ko tod deta hai.

Koi answer ke roop mein len(tails) ki jagah max(tails) return karta hai. Kya galat hai?

Answer tails ki count hai (achievable lengths ki sankhya), na ki sabse badi tail value; max(tails) bas array ka ek element hai.

Koi dp[i] = 0 se initialize karta hai 1 ki jagah. Kya toot jaata hai?

Akela har element length 1 ka increasing subsequence hai, isliye base 1 hona chahiye; 0 se shuru karne par har answer ek se kam ho jaata hai.

Koi claim karta hai ki brute force O(n^2) hai kyunki n^2 pairs of indices (i,j) hain. Ye galat kyun hai?

True brute force har subsequence list karta hai — har element par ek binary choice (rakh/hata do) — isliye ye O(2^n) hai, O(n^2) nahi; n^2 pairs wala figure DP ki cost hai, jo brute force se kahin zyada smart method hai.

Koi LIS ko tails left se right padhkar recover karta hai. Kya galat ho sakta hai?

tails mein values non-adjacent, yahan tak ki out-of-order source positions se aa sakti hain, isliye ye A ki real subsequence nahi bana sakti; stored predecessor indices chahiye.

Why questions

DP state mein subsequence ko index i par khatam karna kyun zaroori hai?

Ye ek global search ko local recurrence mein badalta hai: i par khatam hone wali koi bhi chain pehle wale chhote j par khatam hone wali chain ko extend karti hai, isliye hum sirf backward dekhte hain.

O (n lo g n)

method mein chhoti tail hamesha kam se kam utni hi achhi kyun hoti hai?

Chhoti tail extend karna aasaan hai — zyada future elements isse exceed karte hain — isliye greedily har length ki tail ko minimize karna zyada lambi chains ko zyada baar banane deta hai.

tails ko binary-search kyun kiya ja sakta hai?

Kyunki ye provably hamesha strictly increasing hoti hai, isliye lower_bound (first >= x) well-defined aur correct hai.

DP answer saare dp[i] ka max kyun leta hai ek fixed index ki jagah?

Hume pata nahi kahan optimal LIS khatam hoti hai, isliye hum har position par best ending compute karte hain aur overall maximum lete hain.

tails[k] ko chhote x se replace karna correctness ko kabhi hurt kyun nahi karta?

Ye sirf us length ki recorded tail ko lower karta hai bina length badlaye; chhoti tail har future extension preserve karti hai aur zyada enable bhi karti hai, isliye koi valid answer nahi jaata.

"Card piles" (patience) picture LIS length kyun deta hai?

Piles ki sankhya len(tails) ke barabar hoti hai; har pile ka top us length ki sabse chhoti tail hai, isliye pile count exactly longest increasing pick ki length hai — dekho Patience Sorting.

LIS, LCS se related kyun hai?

LIS(A) = LCS(A, sorted-unique(A)); sorted copy ke saath common subsequence exactly ek increasing subsequence hai — dekho Longest Common Subsequence (LCS).

Russian Doll Envelopes LIS par kyun reduce ho jaata hai?

Width ke hisaab se sort karne ke baad (ties descending height se todte hain), answer heights ka LIS hota hai, isliye 2D nesting problem ek 1D LIS ban jaati hai.

Edge cases

Empty array (n = 0) ka LIS kya hai?

Length 0 — koi elements nahi hain, isliye koi subsequence nahi, aur tails empty rehti hai.

Single-element array [7] (n = 1) ka LIS kya hai?

Length 1 — akela element trivially ek increasing subsequence hai; dp = [1], tails = [7].

Strict increase ke under all-equal array jaise [5,5,5,5] ka LIS kya hai?

Length 1 — koi element strictly doosre se zyada nahi; har x bas tails[0] ko replace karta hai, [5] chhod ke.

Non-decreasing rules ke under [5,5,5,5] ka LIS kya hai?

Length 4 — upper_bound (> x) ke saath equal values append ho jaati hain, poori length expected tarah milti hai.

Algorithm negative numbers ya mixed duplicates ko kaise handle karta hai, e.g. [-1,-1,0]?

Theek hai — comparisons A[j] < A[i] aur lower_bound kisi bhi comparable values par kaam karte hain; strict LIS yahan [-1,0] hai, length 2.

A=[0,1,0,3,2,3] ke liye LIS length kya hai aur beech wala 0 harmless kyun hai?

Length 4 ([0,1,2,3]); doosra 0 tails[0] ko replace karta hai (length-1 tail ko lower karte hue) lekin kisi existing chain ko kabhi short nahi karta.

Connections

Dynamic Programming — "end-here" DP state pattern.
Binary Search — fast method mein lower_bound ko power deta hai.
Patience Sorting — pile count ke liye card-pile intuition.
Greedy Algorithms — "keep smallest tail" ek greedy exchange argument hai.
Longest Common Subsequence (LCS) — LIS as LCS with a sorted copy.
Russian Doll Envelopes — 2D nesting reduced to 1D LIS.