3.7.11 · D1DP problems — Longest Increasing Subsequence (LIS) — O(n²) a
LIS ka matlab hai Longest Increasing Subsequence . Yeh poochta hai: numbers ki ek row mein se, kuch numbers ko cross out karo (baaki ka order mat badlo) taaki jo bachhe woh climbing karte rahein — woh climbing line kitni lambi ho sakti hai? Is topic ki baki saari cheezein bas do tarike hain us ek sawaal ka jawaab jaldi dene ke liye, instead of saare 2ⁿ cross-out patterns try karne ke.
Parent note ko fluently padhne se pehle, tumhe ideas ki ek chhoti si toolbox chahiye. Yeh page har ek idea ko zero se build karta hai, usi order mein jis order mein woh ek doosre par depend karte hain. Yahan kuch bhi assume nahi kiya gaya hai — agar parent ne koi symbol use kiya, toh hum use pehle yahan define karte hain.
Definition LIS — acronym ka poora naamLIS = Longest Increasing Subsequence. "Longest" = hum count ko maximise karte hain; "Increasing" = values ko climb karna chahiye; "Subsequence" = hum unhe doosron ko cross out karke choose karte hain, reorder kiye bina. Teeno words dhyan mein rakho — har ek ek rule hai jise hum neeche precise karte hain.
Is topic ki har cheez ek array ke upar hoti hai — boxes ki ek row, har box mein ek number, aur har box ke neeche ek index (uski position number) hota hai.
A n array values ki ek ordered row hoti hai. Hum ise A Length yeh hai ki usme kitne boxes hain, jise n n = 5
A [ 0 ] 0 se count karte hain, isliye pehla box index 0 par hai, 1 par nahi.)Har box ke neeche ka chhota number uska index hai.
Intuition 0 se count kyun shuru karte hain?Almost har programming language aisa hi karti hai. Index 0 pehla element hai, aur last element index n − 1 n 0 , 1 , 2 , 3 , 4
Common mistake Empty array (n = 0 Yeh ignore karna kyun tempting lagta hai: "kaun empty array dega?" — lekin edge cases real code ko crash kar dete hain. Rule yeh hai: agar A koi box nahi hai (n = 0 koi subsequence nahi hai, isliye LIS length 0 hai . Dono methods ise free mein handle karte hain: O ( n 2 ) d p max tails array empty rehti hai toh uski length 0 hoti hai. Hamesha state karo: empty array → answer 0 .
Yahi THE distinction hai jis par poora topic tika hai.
Definition Subarray (contiguous)Ek subarray ek connected window hoti hai — tum ek start box aur ek end box choose karte ho aur beech mein jo bhi hai sab le lete ho, koi gap nahi. Jaise ek picture frame row ke saath slide karna.
Definition Subsequence (gaps allowed)Ek subsequence woh hai jo bachta hai jab tum kuch boxes ko cross out karo aur baaki ko unke original order mein rakho. Gaps allowed hain. Tum zero boxes cross out kar sakte ho, ya sab bhi.
Picture mein, [3, 4, 5] jo [3,1,4,1,5] se aaya hai, ek valid subsequence hai (humne do 1's cross out kiye) lekin subarray nahi hai (boxes ek doosre ke saath nahi hain).
Common mistake "Reordering allowed hai" — nahi.Yeh tempting kyun lagta hai: aisa feel hota hai jaise tum bas numbers ka ek set pick kar rahe ho. Fix yeh hai: order lock hai. Tum sirf delete kar sakte ho, kabhi shuffle nahi. [5, 3], [3,1,4,1,5] ki subsequence NAHI hai kyunki original mein 5, 3 ke baad aata hai.
Recall Length-n 2 n n O ( 2 n )
Definition Strictly increasingEk sequence strictly increasing hoti hai jab har element apne pehle wale se bada ho — kabhi equal nahi, kabhi chhota nahi. Symbol: neighbours ke beech < sign.
A [ i 1 ] < A [ i 2 ] < ⋯ < A [ i L ] upar ka step hai.
< symbol aur "strict" kya exclude karta hai
x < y x y Strict ka matlab hai hum x = y [2, 2, 3] strictly increasing NAHI hai (do 2's equal hain). Agar hum equals allow karte toh hum non-decreasing kehte aur ≤ strict version hai.
< = strict = "must climb"≤ = loose = "ek step par rest kar sakta hai"lower_bound vs upper_bound choice poori tarah isi do mein se kisi ek ke baare mein hai.
Definition mein i 1 < i 2 < ⋯ < i L < signs chhupe hain — inhe confuse mat karo!
i 1 < i 2 < ⋯ < i L i positions (box numbers) hain, values nahi. i 1 < i 2 i 1 i 2 pehle aati hai". Yeh < order preserved enforce karta hai (no reordering).
Jabki A [ i 1 ] < A [ i 2 ] climbing enforce karta hai.
Toh poori definition mein do rules packed hain:
Order: i 1 < i 2 < ⋯ < i L Climb: A [ i 1 ] < A [ i 2 ] < ⋯ < A [ i L ]
L L count hai — climbing line ki length. LIS sabse bada possible L
Parent ki recurrence yeh hai:
d p [ i ] = 1 + max ( { 0 } ∪ { d p [ j ] : j < i , A [ j ] < A [ i ]} ) .
max max ( S ) S sabse bada number . Agar S max { 0 }
∪ { 0 } ∪ dono collections ko ek mein daal do ". Yahan { 0 } agar koi bhi earlier element qualify na kare , toh max d p [ i ] = 1
{ d p [ j ] : j < i , A [ j ] < A [ i ]} : ko "such that " padho. Yeh kehta hai: "har us j d p [ j ] such that j i aur wahan ki value chhoti hai." Yeh un saari chains ka set hai jise hum A [ i ]
Worked example Poori recurrence ko English mein padhna"Box i i i
d p [ i ] dp dynamic programming ka short form hai: chhote pieces solve karo, unke answers ek table mein store karo, unhe reuse karo. d p [ i ] exactly box i hoti hai." General pattern ke liye Dynamic Programming dekho. Kahan khatam hoti hai yeh pin karna woh trick hai jo ek global hunt ko ek simple left-to-right fill mein badal deti hai.
Definition Big-O notationO ( ⋅ ) kaam kaise grow karta hai , constants ignore karke. O ( n 2 ) n n n O ( n log n ) n
O ( n 2 ) d p [ i ] har earlier j < i dekhna padta hai valid predecessors (A [ j ] < A [ i ] n n har ek ke liye repeat karte hain — ek outer loop. Do nested loops, har ek n n × n = n 2 O ( n 2 ) j O ( log n )
log n log 2 n n Binary Search
tails array
tails O ( n log n ) Patience Sorting ). ==tails[k] = ab tak milne wali length k + 1 hamesha sorted rakhi jaati hai (lambi chain ki tail badi hoti hai), isliye hum ise binary-search kar sakte hain. Ekdum ant mein, len(tails) LIS length ke barabar hoti haitails empty rehti hai, jisse length 0 milti hai. (Warning: tails khud ek real subsequence nahi hai; sirf uski length meaningful hai.)
Ek sorted array par, lower_bound(x) pehle aise element ki position dhundta hai jo ≥ x (x Binary Search se milta hai — har step mein range half karta hai, isliye O ( log n ) tails array par har element ke liye call karta hai yeh decide karne ke liye ki ek tail replace karni hai ya ek nayi append karni hai. upper_bound uska cousin hai: pehla element strictly greater (> x
Array A and index counting from 0
Subsequence delete keep order
Index chain i1 lt i2 order
max union set-builder notation
Dynamic Programming store subproblems
lower_bound and tails array
Seedha parent LIS note mein jaata hai aur aage Patience Sorting aur Greedy Algorithms se connect karta hai.
LIS acronym ka kya matlab hai? Longest Increasing Subsequence.
Length-5 array diya ho toh uske last element ka index kya hai? 4 (indices 0 se n − 1
Empty array (n = 0 0 — climb karne ke liye koi subsequence nahi hai.
Kya [5, 3], [3,1,4,1,5] ki subsequence hai? Kyun ya kyun nahi? Nahi — order lock hai; tum delete kar sakte ho lekin reorder nahi, aur original mein 5, 3 ke baad aata hai.
Length-n 2 n
Kya [2, 2, 3] strictly increasing hai? Nahi — strict equal neighbours forbid karta hai; yeh sirf non-decreasing hai.
i 1 < i 2 Positions (indices) — yeh original order enforce karta hai, value comparison A [ i 1 ] < A [ i 2 ]
dp table se overall LIS length kaise nikalte hain? Saare cells par max lo: LIS = max 0 ≤ i < n d p [ i ]
O ( n 2 ) Ek inner loop har earlier j n n n × n = n 2
Recurrence mein { 0 } Taaki max
log 2 n Kitni baar tum n
Fast method mein tails[k] kya store karta hai? Ab tak dekhi gayi length k + 1
Sorted array par lower_bound(x) kya return karta hai? Pehle aise element ki position jo ≥ x
